基于蜂窝分簇WSN拓扑控制研究
摘要
随着现代微电子技术、无线通信技术、计算机网络技术等长足的进步以及因特网的持续发展,传感器信息获取技术也因此得以迅猛发展。发展方向从单一化模式转向集成化、微型化、智能化以及网络化。目前传感器信息获取技术已成为信息获取领域最重要和最基本的技术之一。
无线传感器网络(Wireless Sensor Network, WSN)技术近些年来广受国际学术界和工业界关注,在工业、军事、环境等领域具有广泛的应用前景。节点定位作为无线传感器网络的关键支撑技术和研究热点,对于无线传感器网络的基本理论方法和应用基础研究都有重要意义。
在WSN中,传感器节点一般都是由电池供电的嵌入式设备构成,具有低成本,体积小等特点。但受到电池供电能力的限制,节点在计算能力和通信能力方面的性能十分有限。因此,网络拓扑结构的重要性对于自组织形式的无线传感器尤为重要。这不仅可以提高网络的路由协议以及MAC协议的效率,还可以在数据的融合、时间同步以及目标的定位等诸多方面提升性能,最终节约能耗延长整个网络的生存周期。所以,无线传感器的网络拓扑结构成为其领域中的一个研究重点。
本文首先介绍了无线传感器的相关概念,阐述了其拓扑控制的研究背景与现状,对WSN的经典分簇算法进行的详细的描述。针对经典的LEACH算法中所存在若干不足之处：分簇不均、簇首节点的选择方式不够合理以及通信的过程中所产生的能耗问题等等,提出了一种基于蜂窝分簇的WSN拓扑控制算法：LEACH-Z算法。该算法将监测区域划分成若干个正六边形子区域,将整个网络划分成蜂窝状结构,让分簇的过程能够尽可能保持均匀；并在簇首节点的生成机制上,充分考虑节点的剩余能量和地理位置两个因素。
由此提出了一种依托中继节点来转发数据信息从而使得簇首节点不必直接与基站节点通信以减少能耗的新机制。再通过利用Network Simulator2(NS2)网络模拟器平台对提出的改进协议进行仿真实验,并将仿真实验的结果与LEACH算法进行比对。实验表明：基于LEACH算法的改进算法——LEACH-Z,节点能量负载均衡化更明显、节点与网络的生存周期更长,网络吞吐量上有显著改进。
With the advancement of microelectronics technology, MEMS, SoC, wireless communication technology, nanometer material, signal processing technology, computer network technology and the rapid development of Internet, the traditional sensor information acquisition technology has developed from the one-way mode to the mode of integration, miniaturization, even to intelligence and networking which has become one of the most important and the most fundamental techniques.
In recent years, the international academic circle and the industry circle have taken great interest in the Wireless Sensor Network (WSN) technology which has wide application prospect in the field of industry, military, environment etc. Node location as the key support technology and research hotspots in wireless sensor networks has great significance to the basic theory and the basic research of application in the Wireless Sensor Network (WSN).
In the WSN, the Sensor Nodes are usually made by the embedded devices which are battery-powered. These Nodes have the low-cost and small cubage features. Because the limitations of the battery supply ability, the Nodes also are limited in the aspects of computation and communication. So the importance of the topology of the network is very significant to the self-coordination WSN. Such thing not only can improve the efficiency of the network routing protocol and MAC protocol, but also can improve so many functions in data fusion, time synchronization and target locating. At last, the life time of the network can be extending. So the network topology of the WSN is becoming one of the focuses of researches in this field.
Firstly, the paper introduces the related concept of the WSN and the Research Overview of the topology control. The classic clustering algorithm of the WSN is also described in detail. The disadvantage of classic LEACH algorithm is analyzed, such as, unevenly clustering, unreasonable choosing of the cluster-head and the energy consumption in communication etc., so that a topology control algorithm for WSN based on cellular clustering is proposed—LEACH-Z algorithm. This algorithm divides the detected area into several regular hexagon sub-areas as the cellular structure to keep the clustering process balance. The nodes'remained energy and locations are fully considered in the cluster-head's generation mechanism.
So, a new mechanism has proposed which relies on the trunk node to transmit the data information in order to make the cluster-head nodes not have to communicate with the BS node directly and to reduce the energy consumption. Then, using the Network Simulator2 (NS2) to have the simulation experiment with the proposed and improved protocol and to compare the outcome of the simulation experiment with the LEACH algorithm. The experiment shows the LEACH-Z algorithm, which is based on the LEACH algorithm, has a more obvious node energy load balancing and a longer time of the node and network lifetime and a remarkable progress of the network throughput.
无线传感器网络(Wireless Sensor Network, WSN)技术近些年来广受国际学术界和工业界关注,在工业、军事、环境等领域具有广泛的应用前景。节点定位作为无线传感器网络的关键支撑技术和研究热点,对于无线传感器网络的基本理论方法和应用基础研究都有重要意义。
在WSN中,传感器节点一般都是由电池供电的嵌入式设备构成,具有低成本,体积小等特点。但受到电池供电能力的限制,节点在计算能力和通信能力方面的性能十分有限。因此,网络拓扑结构的重要性对于自组织形式的无线传感器尤为重要。这不仅可以提高网络的路由协议以及MAC协议的效率,还可以在数据的融合、时间同步以及目标的定位等诸多方面提升性能,最终节约能耗延长整个网络的生存周期。所以,无线传感器的网络拓扑结构成为其领域中的一个研究重点。
本文首先介绍了无线传感器的相关概念,阐述了其拓扑控制的研究背景与现状,对WSN的经典分簇算法进行的详细的描述。针对经典的LEACH算法中所存在若干不足之处：分簇不均、簇首节点的选择方式不够合理以及通信的过程中所产生的能耗问题等等,提出了一种基于蜂窝分簇的WSN拓扑控制算法：LEACH-Z算法。该算法将监测区域划分成若干个正六边形子区域,将整个网络划分成蜂窝状结构,让分簇的过程能够尽可能保持均匀；并在簇首节点的生成机制上,充分考虑节点的剩余能量和地理位置两个因素。
由此提出了一种依托中继节点来转发数据信息从而使得簇首节点不必直接与基站节点通信以减少能耗的新机制。再通过利用Network Simulator2(NS2)网络模拟器平台对提出的改进协议进行仿真实验,并将仿真实验的结果与LEACH算法进行比对。实验表明：基于LEACH算法的改进算法——LEACH-Z,节点能量负载均衡化更明显、节点与网络的生存周期更长,网络吞吐量上有显著改进。
With the advancement of microelectronics technology, MEMS, SoC, wireless communication technology, nanometer material, signal processing technology, computer network technology and the rapid development of Internet, the traditional sensor information acquisition technology has developed from the one-way mode to the mode of integration, miniaturization, even to intelligence and networking which has become one of the most important and the most fundamental techniques.
In recent years, the international academic circle and the industry circle have taken great interest in the Wireless Sensor Network (WSN) technology which has wide application prospect in the field of industry, military, environment etc. Node location as the key support technology and research hotspots in wireless sensor networks has great significance to the basic theory and the basic research of application in the Wireless Sensor Network (WSN).
In the WSN, the Sensor Nodes are usually made by the embedded devices which are battery-powered. These Nodes have the low-cost and small cubage features. Because the limitations of the battery supply ability, the Nodes also are limited in the aspects of computation and communication. So the importance of the topology of the network is very significant to the self-coordination WSN. Such thing not only can improve the efficiency of the network routing protocol and MAC protocol, but also can improve so many functions in data fusion, time synchronization and target locating. At last, the life time of the network can be extending. So the network topology of the WSN is becoming one of the focuses of researches in this field.
Firstly, the paper introduces the related concept of the WSN and the Research Overview of the topology control. The classic clustering algorithm of the WSN is also described in detail. The disadvantage of classic LEACH algorithm is analyzed, such as, unevenly clustering, unreasonable choosing of the cluster-head and the energy consumption in communication etc., so that a topology control algorithm for WSN based on cellular clustering is proposed—LEACH-Z algorithm. This algorithm divides the detected area into several regular hexagon sub-areas as the cellular structure to keep the clustering process balance. The nodes'remained energy and locations are fully considered in the cluster-head's generation mechanism.
So, a new mechanism has proposed which relies on the trunk node to transmit the data information in order to make the cluster-head nodes not have to communicate with the BS node directly and to reduce the energy consumption. Then, using the Network Simulator2 (NS2) to have the simulation experiment with the proposed and improved protocol and to compare the outcome of the simulation experiment with the LEACH algorithm. The experiment shows the LEACH-Z algorithm, which is based on the LEACH algorithm, has a more obvious node energy load balancing and a longer time of the node and network lifetime and a remarkable progress of the network throughput.
引文
[1]刘金娟.无线传感器网络协议及操作系统研究[D].淮南：安徽理工大学,2009.4
[2]于宁.无线传感器网络定位优化方法[D].北京：北京邮电大学,2008.4.
[3]张海波.无线传感器网络中的分簇算法研究[D].济南：山东大学,2007.4.
[4]陆祖建.基于精确地理位置的WSN拓扑控制研究[D].南京：南京航天航空大学,2008.4
[5]何朝笋.传感器网络节点调度算法研究与实现[D].哈尔滨：哈尔滨工业大学,2006.4
[6]王洪奎.无线传感器GAINZ网络实验与设计分析[D].昆明：云南大学,2009.4
[7]李晶.无线传感器网络MAC协议以及路由协议研究[D].合肥：中国科学技术大学,2007.4
[8]曹明华.基于无线传感器网络的环境监测系统设计与应用[D].兰州：兰州理工大学,2009.4
[9]田忠.基于IEEE802.15.4的无线传感器网络验证系统的设计与实现[D].南京：东南大学,2006.4
[10]Akyildiz I F, Su W, Sankarasubramaniam Y. Wireless Sensor Networks:a Survey. Computer Networks,38(4),2002,393-422
[11]刘拥民,蒋新华, 年晓红.无线传感器网络通信协议[J].微电子学与计算机,2007,24(10)：71-73
[12]GUPTA G, YOUNIS M. Load-balanced clustering of wireless sensor networks. Communication,2003. ICC'03. IEEE International conference,2003,1848-1852
[13]于海斌,曾鹏等.智能无线传感器网络系统[M].北京：科学出版社,2006.1
[14]孙利民,李建中,陈渝等.无线传感器网络[M].北京：清华大学出版社,2005.1
[15]HeinZelman W, Chandrakasan A, Balakrishnan H. Energy-Efficient communication protocol for wireless microsensor networks. In:Proc. of the 33rd Annual Hawaii Int'1 Conf. on System Sciences. Maui:IEEE Computer Society,2000.3005-3014
[16]Younis 0, Fahmy S. Heed:A hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks. IEEE Trans. on Mobile Computing,2004,3(4):660-669
[17]Heinzelman W. Application-Specific protocol architectures for wireless networks [Ph.D. Thesis]. Boston:Massachusetts Institute of Technology,2000
[18]Chan H, Perrig A. ACE:An emergent algorithm for highly uniform cluster formation. In:Proc. of the 1st European Workshop on Wireless Sensor Networks. LNCS2920, Berlin:Springer-Verlag,2004.154-171. http://citeseer.ist.psu.edu/672023.html
[19]Gupta I, Riordan D, Sampalli S. Cluster-Head election using fuzzy logic for wireless sensor networks. In:Proc. of the 3rd Annual Communication Networks and Services Research Conf. Halifax:IEEE Computer Society,2005.255-260 http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1429977
[20]李洪兴.变论域自适应模糊控制器[J].中国科学(E辑),1999,29(01)：32-42
[21]沈波,张世永,钟亦平.无线传感器网络分簇路由协议[J].软件学报,2006,17(7)：1588-1600
[22]I. Gupta, D. Riordan, and S. Sampalli. Cluster-head election using fuzzy logic for wireless sensor networks. Proceedings of 3rd Annual Communication Networks and Services Research Conference[EB/OL], Halifax, Canada, July 2005,255-260
[23]Ye M, Li CF, Chen GH, Wu J. EECS:An energy efficient clustering scheme in wireless sensor networks. In:Proc.of the IEEE Int'l Performance Computing and Communications Conf. New York:IEEE Press[EB/OL],2005.535-540 http://www.cse.fau.edu/～jie/research//Publication_files/chen-wu-0 5.pdf
[24]K. Sohrabi, "On Low Power Wireless Sensor Networks," Ph.D. Dissertation, Department of Electrical Engineering, UCLA, June 2000
[25]Fang Q, Zhao F, Guibas LJ. Lightweight sensing and communication protocols for target enumeration and aggregation. In:Proc. of the 4th ACM Int'l Symp. on Mobile Ad Hoc Networking & Computing. ACM Press, 2003.165-176. http://portal.acm.org/citation. cfm?coll=GUIDE&dl=GUIDE&id=778436
[26]Lindsey S, Raghavendra CS. PEGASIS:Power-Efficient gathering in sensor information systems. In:Proc. of the IEEE Aerospace Conf. Montana:IEEE Aerospace and Electronic Systems Society[EB/OL], 2002.1125-1130 http://ceng.use.edu/～raghu/pegasisrev. pdf
[27]Tillapart P, Thumthawatworn T, Pakdeepinit P, Yeophantong T, Charoenvikrom S, Daengdej J. Method for cluster heads selection in wireless sensor networks. In:Proc. of the 2004 IEEE Aerospace Conf. Chiang Mai:IEEE Press,2004.3615-3623 http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29905&arnumb er=1368179&count=72&index=11
[28]Al-Karaki JN, Ul-Mustafa R, Kamal AE. Data aggregation in wireless sensor networks-Exact and approximate algorithms. In:Proc.of the IEEE Workshop on High Performance Switching and Routing. Phoenix:IEEE Communications Society[EB/OL],2004.241-245 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1303478
[29]Lin CR, Gerla M. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 1997,15 (7):1265-1275
[30]娴辑.通信术语面面观[J].军民两用技术与产品,2001,(1)：47
[31]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7)：1282-1291
[32]唐勇,周明天,张欣.无线传感器网络路由协议研究进展[J].软件学报,2006,17(3)：410-421.
[33]陈灿峰.宽带移动互联网[M].北京：北京邮电大学出版社,2005.12
[34]朱智俊,乐孜纯,朱冉.基于NS2的OBS网络仿真平台研究与实现[J].通信学报,2009,30(9)：128-134
[35]KevinFall, Kannan Varadhan. The ns Manual[EB/OL]. (2007-6-29)[2007-7-10] http://www.isi.edu/nsnam/ns/ns-documentation.html.
[36]Francisco Jose Mosqueira Saez. The MIT uAMPS ns Code Extensions Version 1.0[EB/OL].2000.7.1 http://www.mtl.mit. edu/research/icsystems/uamps/research/leach/le achcode.shtml
[37]杜卫林,李斌,田宇.量子退火算法研究进展[J].计算机研究与发展,2008,45(9)：1501-1508
[38]Thomas Williams, Colin Kelley. gnuplot homepage[EB/OL](2007-9-1) [2007-9-20] http://www.gnuplot.info
[39]Wendi Rabiner Heinzelman, Anantha Chandrakasan, Hari Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]. In:Proc.33rd Annual Hawaii International Conference on System Sciences,2000:3005-3014
[40]Jianping Pany Y, Thomas Hou, Lin Cai, etc. Topology Control for Wireless Sensor Networks[C]. In:International Conference on Mobile Computing and Networking. Proceedings of the 9th annual international conference on Mobile computing and networking[EB/OL],2003:286-299. http://mtlweb.mit.edu/researchgroups/icsystems/uamps/research/lea ch/leach_code.shtml
[41]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Annual Hawaii International Conference,2000,10 pp
[2]于宁.无线传感器网络定位优化方法[D].北京：北京邮电大学,2008.4.
[3]张海波.无线传感器网络中的分簇算法研究[D].济南：山东大学,2007.4.
[4]陆祖建.基于精确地理位置的WSN拓扑控制研究[D].南京：南京航天航空大学,2008.4
[5]何朝笋.传感器网络节点调度算法研究与实现[D].哈尔滨：哈尔滨工业大学,2006.4
[6]王洪奎.无线传感器GAINZ网络实验与设计分析[D].昆明：云南大学,2009.4
[7]李晶.无线传感器网络MAC协议以及路由协议研究[D].合肥：中国科学技术大学,2007.4
[8]曹明华.基于无线传感器网络的环境监测系统设计与应用[D].兰州：兰州理工大学,2009.4
[9]田忠.基于IEEE802.15.4的无线传感器网络验证系统的设计与实现[D].南京：东南大学,2006.4
[10]Akyildiz I F, Su W, Sankarasubramaniam Y. Wireless Sensor Networks:a Survey. Computer Networks,38(4),2002,393-422
[11]刘拥民,蒋新华, 年晓红.无线传感器网络通信协议[J].微电子学与计算机,2007,24(10)：71-73
[12]GUPTA G, YOUNIS M. Load-balanced clustering of wireless sensor networks. Communication,2003. ICC'03. IEEE International conference,2003,1848-1852
[13]于海斌,曾鹏等.智能无线传感器网络系统[M].北京：科学出版社,2006.1
[14]孙利民,李建中,陈渝等.无线传感器网络[M].北京：清华大学出版社,2005.1
[15]HeinZelman W, Chandrakasan A, Balakrishnan H. Energy-Efficient communication protocol for wireless microsensor networks. In:Proc. of the 33rd Annual Hawaii Int'1 Conf. on System Sciences. Maui:IEEE Computer Society,2000.3005-3014
[16]Younis 0, Fahmy S. Heed:A hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks. IEEE Trans. on Mobile Computing,2004,3(4):660-669
[17]Heinzelman W. Application-Specific protocol architectures for wireless networks [Ph.D. Thesis]. Boston:Massachusetts Institute of Technology,2000
[18]Chan H, Perrig A. ACE:An emergent algorithm for highly uniform cluster formation. In:Proc. of the 1st European Workshop on Wireless Sensor Networks. LNCS2920, Berlin:Springer-Verlag,2004.154-171. http://citeseer.ist.psu.edu/672023.html
[19]Gupta I, Riordan D, Sampalli S. Cluster-Head election using fuzzy logic for wireless sensor networks. In:Proc. of the 3rd Annual Communication Networks and Services Research Conf. Halifax:IEEE Computer Society,2005.255-260 http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1429977
[20]李洪兴.变论域自适应模糊控制器[J].中国科学(E辑),1999,29(01)：32-42
[21]沈波,张世永,钟亦平.无线传感器网络分簇路由协议[J].软件学报,2006,17(7)：1588-1600
[22]I. Gupta, D. Riordan, and S. Sampalli. Cluster-head election using fuzzy logic for wireless sensor networks. Proceedings of 3rd Annual Communication Networks and Services Research Conference[EB/OL], Halifax, Canada, July 2005,255-260
[23]Ye M, Li CF, Chen GH, Wu J. EECS:An energy efficient clustering scheme in wireless sensor networks. In:Proc.of the IEEE Int'l Performance Computing and Communications Conf. New York:IEEE Press[EB/OL],2005.535-540 http://www.cse.fau.edu/～jie/research//Publication_files/chen-wu-0 5.pdf
[24]K. Sohrabi, "On Low Power Wireless Sensor Networks," Ph.D. Dissertation, Department of Electrical Engineering, UCLA, June 2000
[25]Fang Q, Zhao F, Guibas LJ. Lightweight sensing and communication protocols for target enumeration and aggregation. In:Proc. of the 4th ACM Int'l Symp. on Mobile Ad Hoc Networking & Computing. ACM Press, 2003.165-176. http://portal.acm.org/citation. cfm?coll=GUIDE&dl=GUIDE&id=778436
[26]Lindsey S, Raghavendra CS. PEGASIS:Power-Efficient gathering in sensor information systems. In:Proc. of the IEEE Aerospace Conf. Montana:IEEE Aerospace and Electronic Systems Society[EB/OL], 2002.1125-1130 http://ceng.use.edu/～raghu/pegasisrev. pdf
[27]Tillapart P, Thumthawatworn T, Pakdeepinit P, Yeophantong T, Charoenvikrom S, Daengdej J. Method for cluster heads selection in wireless sensor networks. In:Proc. of the 2004 IEEE Aerospace Conf. Chiang Mai:IEEE Press,2004.3615-3623 http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29905&arnumb er=1368179&count=72&index=11
[28]Al-Karaki JN, Ul-Mustafa R, Kamal AE. Data aggregation in wireless sensor networks-Exact and approximate algorithms. In:Proc.of the IEEE Workshop on High Performance Switching and Routing. Phoenix:IEEE Communications Society[EB/OL],2004.241-245 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1303478
[29]Lin CR, Gerla M. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 1997,15 (7):1265-1275
[30]娴辑.通信术语面面观[J].军民两用技术与产品,2001,(1)：47
[31]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7)：1282-1291
[32]唐勇,周明天,张欣.无线传感器网络路由协议研究进展[J].软件学报,2006,17(3)：410-421.
[33]陈灿峰.宽带移动互联网[M].北京：北京邮电大学出版社,2005.12
[34]朱智俊,乐孜纯,朱冉.基于NS2的OBS网络仿真平台研究与实现[J].通信学报,2009,30(9)：128-134
[35]KevinFall, Kannan Varadhan. The ns Manual[EB/OL]. (2007-6-29)[2007-7-10] http://www.isi.edu/nsnam/ns/ns-documentation.html.
[36]Francisco Jose Mosqueira Saez. The MIT uAMPS ns Code Extensions Version 1.0[EB/OL].2000.7.1 http://www.mtl.mit. edu/research/icsystems/uamps/research/leach/le achcode.shtml
[37]杜卫林,李斌,田宇.量子退火算法研究进展[J].计算机研究与发展,2008,45(9)：1501-1508
[38]Thomas Williams, Colin Kelley. gnuplot homepage[EB/OL](2007-9-1) [2007-9-20] http://www.gnuplot.info
[39]Wendi Rabiner Heinzelman, Anantha Chandrakasan, Hari Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]. In:Proc.33rd Annual Hawaii International Conference on System Sciences,2000:3005-3014
[40]Jianping Pany Y, Thomas Hou, Lin Cai, etc. Topology Control for Wireless Sensor Networks[C]. In:International Conference on Mobile Computing and Networking. Proceedings of the 9th annual international conference on Mobile computing and networking[EB/OL],2003:286-299. http://mtlweb.mit.edu/researchgroups/icsystems/uamps/research/lea ch/leach_code.shtml
[41]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Annual Hawaii International Conference,2000,10 pp