Scheduling on sensor hybrid network
Scheduling on sensor hybrid network
复制标题
DOI：
10.1109/icccn.2005.1523924
复制
发表时间：
2005-10
期刊：
影响因子：
--
通讯作者：
Hongsik Choi;Ju Wang;E. Hughes
中科院分区：
文献类型：
--
作者：
Hongsik Choi;Ju Wang;E. Hughes
我们研究了一个独特的调度问题，在无线传感器网络中，在一个集群中的所有节点只发送一个数据包到一个指定的汇聚节点的目标是最小化的传输时间。困难在于节点传输必须在时间或空间上充分隔离以避免冲突。该问题是制定和解决通过图形表示。我们证明，与特定的网络拓扑结构（无论是线或树），一个最佳的传输时间表可以有效地通过一个流水线式的时间表。具有n个节点的线（或树）拓扑所需的最小时间为3（n-2）。我们进一步证明，我们的调度问题是NP-困难的一般图。我们提出了一般图的启发式算法。我们的启发式算法尝试调度尽可能多的独立段，以增加并行传输的程度。该算法相比，RTS/CTS基于分布式算法。初步的模拟结果表明，我们的启发式算法优于RTS/CTS的分布式算法（高达30%），并表现出稳定的调度行为。
We investigate a unique scheduling problem in wireless sensor networks where all nodes in a cluster send exactly one packet to a designated sink node with goal of minimized transmission time. The difficulty lies in the fact that node transmissions must be sufficiently isolated either in time or in space to avoid collisions. The problem is formulated and solved via graph representation. We prove that with specific network topologies (either line or tree); an optimal transmission schedule can be obtained efficiently through a pipeline-like schedule. The minimum time required for a line (or tree) topology with n nodes is 3(n-2). We further prove that our scheduling problem is NP-hard for general graphs. We propose a heuristic algorithm for general graphs. Our heuristic tries to schedule as many independent segments as possible to increase the degree of parallel transmission. This algorithm is compared to an RTS/CTS based distributed algorithm. Preliminary simulated results indicate that our heuristic algorithm out-performs the RTS/CTS based distributed algorithm (up to 30%) and exhibits stable scheduling behavior.