Energy Efficient Backoff Hierarchical Clustering Algorithms for Multi-Hop Wireless Sensor Networks
-
摘要: 1．本文的创新点
本文设计了一种全新的基于自适应退避策略的分簇算法，并开创性地将其应用于多跳无线传感器网络，数学分析与仿真实验都证明这种算法的能量有效性好于经典算法。同时在此基础之上，进一步提出了层次型分簇协议模型，从而为大规模传感器网络的有效管理和数据的高效通信提供了可行的方法，目前大规模传感器网络的研究国内外并不多见。 2．实现方法
无线传感器网络的分簇算法和平面路由协议不同，是基于轮次的，每一轮分为“选举期”和“稳定期”。在“选举期”，传感器节点通过选举算法选出簇头，簇头组织节点形成层次型结构；在“稳定期”，节点将所探测到的信息发送到簇头，簇头完成数据融合后发送至基站（Sink节点）。本算法中，在选举期，所有的节点开始的时候都处于等待状态，等待一个随机的时间间隔 ti
ti=-(1/λi)ln(1-χi)
χi 是一个均匀分布在 [0,1]区间上的随机变量，所以ti 也是一个随机变量，其概率分布函数是ƒ(ti)=λie-λiti ，λi=α(Eires)/(Emax)，这里α 是一个常数。当某个节点的定时时间到达的时候，也就是意味着这段时间之内它没有收到邻居节点的广播消息，它决定自己成为簇头，并发送ADV_CH消息。如果目标是形成一个k-hop的传感器网络，该消息最多被转发k-1次。 当其它节点收到ADV_CH消息，节点就停止自己的定时器，成为从属节点，并在自己的路由表中记录收到的这条消息，完成后加以转发。 当TCF , 预先设定的最长簇形成时间到达的时候，一个从属节点根据与簇头的距离决定加入某一个簇，广播一个JOIN消息来表明自己的决定， 中间节点查找自己的路由表来转发这个消息，直到该消息到达目的的簇头。簇头记录下所有从属节点的消息，形成了自己管理的簇。而那些没有收到ADV_CH 消息的节点将成为“强迫型簇头”，被迫与远端的基站直接通信。
层次型退避分簇算法是对以上算法的扩展，采用自底向上的方法，，level-1 的簇头首先从整个网络被选举出来，接下来leveel-2 的簇头从level-1的簇头中选举而生，以此类推，直到到达最高层次的簇头，最高层次的簇头形成主干网，实现最高级别的数据融合和通信。 3．结论及未来待解决的问题
这篇论文我们提出了一种分布式的算法来组织多跳传感器网络，从而实现全网的高能效以及层次型管理，延长网络生命。该算法充分考虑了节点剩余能量，所以提出的自适应退避策略能够有效地实现负载均衡，并保证选举产生的簇头均匀分布，避免产生过多的节点与基站长距离通信。数学分析也充分证明了这一点，而且该算法还具有实现简单和O(1) 的时间复杂性等特点。仿真实验表明该算法比之前的经典算法能够提高30%的能量效率。同时本文还将这个算法扩展到多层次型结构也有非常现实的意义，因为大规模无线传感器网络的研究越来越受到国内外学者的重视。
这篇论文提出的算法中使用的某些参数并没有经过严格的数学推导，而是依赖于实验数据，所以参数的选择未必是最优值。同时该算法都是假设通信环境是理想的，但实际情况下通信信道是会有错误和噪声的，这些都是将来需要考虑解决的问题 4．实用价值或应用前景
无线传感器网络越来越受到国内外学术界和工业界的重视，特别是物联网概念的提出和发展之后。该分簇算法简单有效，非常适用于环境监测，军事信息采集，野外动植物研究等周期性工作的传感器网络场景，具有高效能和管理简单的特点，同时不依赖于复杂的节点硬件，不需要复杂的调节发射功率等装置，使其应用更为广泛。Abstract: Compared with flat routing protocols, clustering is a fundamental performance improvement technique in wireless sensor networks, which can increase network scalability and lifetime. In this paper, we integrate the multi-hop technique with a backoff-based clustering algorithm to organize sensors. By using an adaptive backoff strategy, the algorithm not only realizes load balance among sensor node, but also achieves fairly uniform cluster head distribution across the network. Simulation results also demonstrate our algorithm is more energy-efficient than classical ones. Our algorithm is also easily extended to generate a hierarchy of cluster heads to obtain better network management and energy-efficiency. -
-
[1] Akyildiz I F, Su W, Sankarasubramaniam Y et al. A survey on sensor networks. IEEE Communications Magazine, 2002, 40(8): 102-114.
[2] Zhao F, Guibas L. Wireless Sensor Networks: An Information Processing Approach. Morgan Kaufmann, 2004.
[3] Pottie G J, Kaiser W J. Wireless integrated network sensors. Communications of the ACM, 2000, 43(5): 51-58.
[4] Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks. IEEE Tran. Wireless Communications, Oct. 2002, 1(4): 660-670.
[5] Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proc. ACM/IEEE Int. Conf. Mobile Computing and Networking (MOBICOM), Boston, USA, Aug. 6-11, 2000, pp.56-67.
[6] Younis O, Fahmy S. Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach. In Proc. IEEE INFOCOM, Hong Kong, China, Mar. 7-11, 2004.
[7] Cao Y, He C. A distributed clustering algorithm with an adaptive backoff strategy for wireless sensor networks. IEICE Transactions on Communications., 2006, 89-B(2): 609-613.
[8] Amis A D, Prakash R, Vuong T H P, Huynh D T. Max-Min D-cluster formation in wireless ad hoc networks. In Proc. IEEE INFOCOM2000, Tel Aviv, Israel, Mar. 26, 2000, pp.32-41.
[9] Bandyopadhyay S, Coyle E J. An energy efficient hierarchical clustering algorithm for wireless sensor networks. In Proc. IEEE INFOCOM2003, San Francisco, USA, Mar. 30-Apr. 3, April 2003, pp.1713-1723.
[10] Sundararaman B, Buy U, Kshemkalyani A D. Clock synchronization for wireless sensor networks: A survey. Ad Hoc Networks, 2005, 3(3): 281-323.
[11] Chen Y P, Liestman A L, Liu J. A hierarchical energy-efficient framework for data aggregation in wireless sensor networks. IEEE Trans. VT, May, 2006, 55(3): 789-796.
[12] Yu M, Leung K K, Malvankar A. A dynamic clustering and energy efficient routing technique for sensor networks. IEEE Transactions on Wireless Communications, Aug. 2007, 6(8): 3069-3079.
计量
- 文章访问数: 30
- HTML全文浏览量: 4
- PDF下载量: 2568
下载:
