無線感測網路中負載平衡的群聚演算法

Clustering with Dynamic Load Balancing in Wireless Sensor Networks

姚佳妏(Chia-Wen Yao)

指導教授 ： 廖婉君

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2005年)

https://doi.org/10.6342/NTU.2005.01384

摘要

無線感測網路的特性之一便是能源受限制且分佈範圍廣大。如果節省及有效利用無線感測網路的能源已變成一重要的討論議題。研究顯示，如果無線感測網路缺乏負載平衡的機制，有些節點可能會負荷比別的節點更繁重的流量，造成這些節點能源耗損快速，並加速這些節點的死亡。一旦這些節點死亡，其他的節點必須消耗更多的能量來維持與原來相同的連線能力與覆蓋範圍，於是同一地區的節點將會一個接一個快速死亡。當整個網路癱瘓時，我們會發現，仍然存在某些節點其剩餘相當充足的能量。所以如果能將能量消耗平均分散給網路中的節點，對於延長無線感測網路的存活時間將有相當大的幫助。在這篇論文中，我們提出了一能有效達到能源利用與負載平衡的演算法。我們的演算法是完全分散式且能動態調整負載的演算法，不需要其他任何的假設與控制，便能在任何無線隨意網路中執行。模擬結果顯示，我們的演算法真的能有效平衡負載且延長網路的存活時間。

關鍵字

無線感測網路 ； 負載平衡 ； 群聚演算法

並列摘要

Since the sensor networks is large scale and energy constrained, how to reserve and use energy efficiency is an important issue. It is found that if there is lack of load balancing schemes, some nodes in the sensor networks will suffer heavy traffic load and die soon. Once nodes die, other nodes must consume more energy to maintain connectivity and coverage. At the end of the network lifetime, there will be some nodes that still have sufficient energy, but the network can’t work anymore. So, if we can evenly distribute the energy consumption to nodes in the sensor networks, the network lifetime is expected to be longer. In this thesis, we present an energy-efficiency and load balancing algorithm that can help to balance the load of cluster heads and reduce such unnecessary energy consumption. From the simulation result, the load of cluster heads will tend to the mean value, and the network lifetime can be improved.

並列關鍵字

sensor network ； load balancing ； clustering

參考文獻

[2] D.J Baker and A. Ephremides, “The Architectural Organization of a Mobile Radio Networks Via a Distributed Algorithm”, IEEE Transactions on Communications, Vol 29 No.11 pp. 1694-1701

[5] A. D. Amis, R. Prakash, T. H. P. Vuong and D. T. Huynh, “Max-Min D-Cluster Formation in Wireless Ad Hoc Networks”, in Proceedings of IEEE INFOCOM, March 2000

[6] S.Banerjee, S.Khuller. A Clustering Scheme for Hierarchical Control in Multi-hop Wireless Networks. Technical Report CS-TR-4103, University

[7] C.F. Chiasserini, I. Chlamtac, P. Monti and A. Nucci, “Energy Efficient design of Wireless Ad Hoc Networks”, in Proceddings of European Wireless, February 2002.

[8] A. Ephremides, J.E. Wieselthier and D. J. Baker, “A Design concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling”, Proceeding of IEEE, Vol. 75 No1, pp.56-73, 1987