无线传感器网络中基于梯度的有网关分簇拓扑控制研究
|
摘要
无线传感器网络(Wireless Sensor Network, WSN)是由大量随机分布的集成有传感器单元、数据处理单元和通信单元的微小节点,通过自组织的方式构成的无线网络。
鉴于无线传感器网络多跳传输的特点,其路由协议的设计与现有通信网络的路由协议不同,尤其网络节点在一次性播撒的情况下,节点能量是不可再生的,因此,提高平衡网络能量消耗、延长网络生命周期成为无线传感器网络的首要设计目标。目前无线传感器网络核心的路由协议是分簇路由协议,而作为分簇路由协议的基础-多级簇树拓扑结构由于其能耗小,寿命长的特点已成为近年来无线传感器网络的一个研究热点。
本文介绍一种基于梯度的分簇拓扑控制算法ETBG(energy-aware topology control protocol based on gradient),该算法通过基站将网络划分为若干个半圆形的梯度场,节点间根据权值大小及梯度等级组成簇树,此算法时延较小,但是所用权值单一,未考虑距离在节点数据传输时的耗能情况,部分簇内节点之间相距过远,造成通信耗能过大。
针对ETBG算法存在的问题,本文提出一种基于梯度的有网关多级簇树算法,在节点分簇时设计一个调节因子在剩余能量和距离之间进行调节,在成簇的过程中,采用综合权值大的节点作为簇头节点。同时利用负载均衡的思想调节各个簇头的簇成员数目,使各个簇头的簇成员数目更加均衡,耗能更加平均。最后在簇头之间加入网关根据梯度等级建立簇树,能解决ETBG算法在簇头距离过远情况下直接通信耗能过高的弊端,同时能减少网内簇头的数目,通过簇头轮换策略,可以延长网络的生命周期。本文还考虑给出该算法的局部维护和更新策略,使该算法在出现局部拓扑变化时,可以迅速使各个节点建立连接,能保证网络的正常运行,提高算法的自适应性。
Wireless sensor networks (WSN), which is constituted by a large number of randomly distributed micro nodes with a self-organization way, including the integrated sensor unit, the data processing unit and the communication unit.
In view of the multi-hop transmission characteristics of the wireless sensor network, there is obvious difference in the routing protocols design with existing communications networks, especially in the case that the entire network nodes are disposable sown and the node energy is non-renewable. Therefore, improving the energy consumption of the balance the network and prolonging the network life cycle became the primary goal for wireless sensor networks design. Presently, the cluster-based routing protocols is the core of the wireless sensor network routing protocol, and the multistage cluster tree topology structure, as the foundation of the cluster-based routing protocols, had become a research hotspot in wireless sensor networks due to its low energy consumption and long life characteristics in recent years.
A new algorithm, called ETBG (energy-aware topology control protocol based on gradient) was introduced in this paper. In this algorithm, the network was divided into a plurality of semi-circular gradient field according to the base station, and the nodes was combined together to form cluster tree based on the value of the weights between nodes and the gradient grade composition. Smaller delay was the advantage of this algorithm, but the weakness that energy loss increased with increasing distance between parts of the nodes was obvious, too. Because the weight in the algorithm was single and the energy consumption of the nodes in long distance data transmission was out of considering.
To solve this problem, a hierarchical clustering algorithm based on the gradient with a gateway had been proposed in this paper. A regulator was set in node clustering to adjust the residual energy and the distance of the nodes, ensuring the node with high comprehensive weight value to be the cluster head node. Meanwhile, the members of each cluster head had been optimized based on load balancing. Finally the gateway was added to the cluster head to established cluster tree according gradient grade.So the disadvantages of the ETBG that energy loss increased severely with increasing distance between cluster head nodes was avoided, and the number of network cluster head was reduced. Meanwhile, the network life cycle was prolonged due to the cluster head rotation strategy. In addition, the local maintenance and updating strategy of the algorithm was proposed,so that the nodes could establish a connection with each other rapidly when the local topology was changed, which ensured the normal operation of the network and improved the adaptively of the algorithm.
鉴于无线传感器网络多跳传输的特点,其路由协议的设计与现有通信网络的路由协议不同,尤其网络节点在一次性播撒的情况下,节点能量是不可再生的,因此,提高平衡网络能量消耗、延长网络生命周期成为无线传感器网络的首要设计目标。目前无线传感器网络核心的路由协议是分簇路由协议,而作为分簇路由协议的基础-多级簇树拓扑结构由于其能耗小,寿命长的特点已成为近年来无线传感器网络的一个研究热点。
本文介绍一种基于梯度的分簇拓扑控制算法ETBG(energy-aware topology control protocol based on gradient),该算法通过基站将网络划分为若干个半圆形的梯度场,节点间根据权值大小及梯度等级组成簇树,此算法时延较小,但是所用权值单一,未考虑距离在节点数据传输时的耗能情况,部分簇内节点之间相距过远,造成通信耗能过大。
针对ETBG算法存在的问题,本文提出一种基于梯度的有网关多级簇树算法,在节点分簇时设计一个调节因子在剩余能量和距离之间进行调节,在成簇的过程中,采用综合权值大的节点作为簇头节点。同时利用负载均衡的思想调节各个簇头的簇成员数目,使各个簇头的簇成员数目更加均衡,耗能更加平均。最后在簇头之间加入网关根据梯度等级建立簇树,能解决ETBG算法在簇头距离过远情况下直接通信耗能过高的弊端,同时能减少网内簇头的数目,通过簇头轮换策略,可以延长网络的生命周期。本文还考虑给出该算法的局部维护和更新策略,使该算法在出现局部拓扑变化时,可以迅速使各个节点建立连接,能保证网络的正常运行,提高算法的自适应性。
Wireless sensor networks (WSN), which is constituted by a large number of randomly distributed micro nodes with a self-organization way, including the integrated sensor unit, the data processing unit and the communication unit.
In view of the multi-hop transmission characteristics of the wireless sensor network, there is obvious difference in the routing protocols design with existing communications networks, especially in the case that the entire network nodes are disposable sown and the node energy is non-renewable. Therefore, improving the energy consumption of the balance the network and prolonging the network life cycle became the primary goal for wireless sensor networks design. Presently, the cluster-based routing protocols is the core of the wireless sensor network routing protocol, and the multistage cluster tree topology structure, as the foundation of the cluster-based routing protocols, had become a research hotspot in wireless sensor networks due to its low energy consumption and long life characteristics in recent years.
A new algorithm, called ETBG (energy-aware topology control protocol based on gradient) was introduced in this paper. In this algorithm, the network was divided into a plurality of semi-circular gradient field according to the base station, and the nodes was combined together to form cluster tree based on the value of the weights between nodes and the gradient grade composition. Smaller delay was the advantage of this algorithm, but the weakness that energy loss increased with increasing distance between parts of the nodes was obvious, too. Because the weight in the algorithm was single and the energy consumption of the nodes in long distance data transmission was out of considering.
To solve this problem, a hierarchical clustering algorithm based on the gradient with a gateway had been proposed in this paper. A regulator was set in node clustering to adjust the residual energy and the distance of the nodes, ensuring the node with high comprehensive weight value to be the cluster head node. Meanwhile, the members of each cluster head had been optimized based on load balancing. Finally the gateway was added to the cluster head to established cluster tree according gradient grade.So the disadvantages of the ETBG that energy loss increased severely with increasing distance between cluster head nodes was avoided, and the number of network cluster head was reduced. Meanwhile, the network life cycle was prolonged due to the cluster head rotation strategy. In addition, the local maintenance and updating strategy of the algorithm was proposed,so that the nodes could establish a connection with each other rapidly when the local topology was changed, which ensured the normal operation of the network and improved the adaptively of the algorithm.
引文
[1]李善仓,张克望,无线传感器网络原理与应用,机械工业出版社,2008,3
[2]于宏毅,李鸥,张效义,无线传感器网络理论、技术与实现,国防工业出版社,2008,9
[3]崔莉,鞠海玲,苗勇等,无线传感器网络研究进展,计算机研究与发展,2005,
[4]Harirong Qi, Phani Teja Kuruganti, Yingyue Xu. The development of localized algorithms in the wireless sensor networks, Sensor Journal,2002,2(7):286-293
[5]L.Girod, VBychkovskiy,J.Elson, D.Estrin, Locating tiny sensors in time and space:A case study, Proceedings of the International Conference on Computer Design.2002,195-204
[6]郭睿,郭伟,刘军.一种多信道AdHoc网络的多径负载均衡路由协议[J].计算机科学,2010,(07)：118-121.
[7]杨双懋,郭伟,唐伟.一种最大化网络吞吐量的认知无线AdHoc网络跨层优化算法[J].计算机学报,2012,(03)：491-503.
[8]YanhuaiQu, JiananFang, ShuaiZhang. Identifying Neighborand Connectivity of Wireless Sens or Networks with Poisson Point Process [J]. Wireless Personal Communications,2012, 64(4):795-809.
[9]Guang-yu Fan,Huifang Chen,Lei Xie,Kuang Wang. Funneling media access control (MAC) protocol for underwater acoustic sensor networks.[J],Journal of Zhejiang University-Science C,2011,12:932-941
[10]周丽敏.无线传感器网络MAC协议的研究和设计.硕士学位论文,西安,2007.1
[11]蹇强,龚正虎，朱培栋，桂春梅.无线传感器网络MAC协议研究进展[J1.软件学报,2008,02：389-403.
[12]S.C. Wang, C. S. Shiao, K. Q. Yan and S. S. Wang, "A Secure Wireless Sensor Network by Trusted Timely Computing Base,"Proceedings of 18th Annual Conference International Information Management Association,2007, pp.57-63
[13]王金龙,王呈贵,阚春荣等.无线超宽带(UWB)通信原理与应用.北京：人民邮电出版社,2005：2～3
[14]周晓光,王晓华.射频识别(RFID)技术原理与应用实例.北京：人民邮电出版社,2006：1-3
[15]何云珍,孙增友.无线自组传感器网络研究与应用.东北电力大学学报,2006.12
[16]M. Sharifi, M.A. Taleghan and A. Taherkordi,"A Middleware Layer Mechanism for QoS Support in Wireless Sensor Networks," Proceedings of the Systems and International Conference on Mobile Communications and Learning Technologies,2006, pp.118-118
[17]GPei and C.Chien, Low power TDMA in Large Wireless Sensor Networks, Military Communications Conference, Communications for Network-Centric Operations:Creating the Information Force,2001,1:28-31.
[18]Woo, D.Culler, A transmission control scheme for media access in sensor networks, Proceedings of the ACM MobiCom 2001,221-235.
[19]L. Qing, Q. Zhu, and M. Wang,"Design of a Distributed Energy-efficient Clustering Algorithm for Heterogeneous Wireless Sensor Networks,"Computer Communications, 2006, Vol.29, Issue 12, pp.2230-2237
[20]S.Capkun, J.P.Hubaux, and Levente Buttyan, Mobility Helps Security in Ad Hoc Networks, Proceedings of MobiHOC,2003,46-56.
[21]李田,史浩山,杨俊刚.无线传感器网络LEACH协议成簇算法研究[J].传感技术学报,2010,(08)：1158-1162.
[22]A. Manjeshwar and D. P. Agrawal, "TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks," Proceedings of the 1st International Workshop on Parallel and Distribute d Computing Issues in Wireless Networks and Mobile Computing,2001, pp.2009-2015.
[23]S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin and A. O. Fapojuwo,"A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks,"IEEE Radio Communications Magazine,2005, Vol.43, Issue 3, pp.8-13.
[24]J. Qiangfeng and D. Manivannan, "Routing Protocols for Sensor Networks," Proceedings of the Consumer Communications and Networking Conference,2004, pp.93-98.
[25]M. G Rezaie, V. S. Mansouri and M. Mani, "Critical Area Attention in Traffic Aware Dynamic Node Scheduling for Low Power Sensor Networks," Proceedings of the Wireless Communications and Networking Conference,2005, Vol.4, pp.1933-1938.
[26]Philip Levis and David Culler, Mate:a Tiny Virtual Machine for Sensor Networks, Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X), ACM Press,2002,85-95.
[27]R. Shah and J. Rabaey, " Energy Aware Routing for Low Energy Ad Hoc Sensor Networks," Proceedings of the IEEE Wireless Communications and Networking Conference,2002, Vol. 1, pp.350-355
[28]张源.一种TEEN协议的节能型改进算法[J].现代计算机(专业版),2009,(05)：61-64.
[29]D. Braginsky and D. Estrin, "Rumor Routing Algorithm for Sensor Networks," Proceedings of the First Workshop on Sensor Networks and Applications,2002, pp.22-31
[30]段磊.无线传感器网络基于梯度的分级簇算法研究[D].[硕士学位论文].郑州：郑州大学,2009
[31]阎新芳,段磊,李腾.无线传感器网络中基于梯度的拓扑控制算法[J].计算机工程与应用,2011,(02)：95-98.
[32]A.Wang, W. B. Heinzelmen, A. Sinha and A. P. Chanderkasan, Energy-scalable protocols for battery-operated microsensor networks, Journal of VLSI Signal Processing,2001,29: 223-237.
[33]阎新芳,孙雨耕,赵承利,无线传感器网络中基于能量的分级簇算法[J],天津大学学报,2005,38(12)：1106-1110
[34]Perillo M, Zhao C, Heinzelman W.On the problem of unbalanced load distribution in wireless sensor networks[C], Globe Com Workshops 2004.[S.1.]:IEEE,2004:74-79.
[2]于宏毅,李鸥,张效义,无线传感器网络理论、技术与实现,国防工业出版社,2008,9
[3]崔莉,鞠海玲,苗勇等,无线传感器网络研究进展,计算机研究与发展,2005,
[4]Harirong Qi, Phani Teja Kuruganti, Yingyue Xu. The development of localized algorithms in the wireless sensor networks, Sensor Journal,2002,2(7):286-293
[5]L.Girod, VBychkovskiy,J.Elson, D.Estrin, Locating tiny sensors in time and space:A case study, Proceedings of the International Conference on Computer Design.2002,195-204
[6]郭睿,郭伟,刘军.一种多信道AdHoc网络的多径负载均衡路由协议[J].计算机科学,2010,(07)：118-121.
[7]杨双懋,郭伟,唐伟.一种最大化网络吞吐量的认知无线AdHoc网络跨层优化算法[J].计算机学报,2012,(03)：491-503.
[8]YanhuaiQu, JiananFang, ShuaiZhang. Identifying Neighborand Connectivity of Wireless Sens or Networks with Poisson Point Process [J]. Wireless Personal Communications,2012, 64(4):795-809.
[9]Guang-yu Fan,Huifang Chen,Lei Xie,Kuang Wang. Funneling media access control (MAC) protocol for underwater acoustic sensor networks.[J],Journal of Zhejiang University-Science C,2011,12:932-941
[10]周丽敏.无线传感器网络MAC协议的研究和设计.硕士学位论文,西安,2007.1
[11]蹇强,龚正虎，朱培栋，桂春梅.无线传感器网络MAC协议研究进展[J1.软件学报,2008,02：389-403.
[12]S.C. Wang, C. S. Shiao, K. Q. Yan and S. S. Wang, "A Secure Wireless Sensor Network by Trusted Timely Computing Base,"Proceedings of 18th Annual Conference International Information Management Association,2007, pp.57-63
[13]王金龙,王呈贵,阚春荣等.无线超宽带(UWB)通信原理与应用.北京：人民邮电出版社,2005：2～3
[14]周晓光,王晓华.射频识别(RFID)技术原理与应用实例.北京：人民邮电出版社,2006：1-3
[15]何云珍,孙增友.无线自组传感器网络研究与应用.东北电力大学学报,2006.12
[16]M. Sharifi, M.A. Taleghan and A. Taherkordi,"A Middleware Layer Mechanism for QoS Support in Wireless Sensor Networks," Proceedings of the Systems and International Conference on Mobile Communications and Learning Technologies,2006, pp.118-118
[17]GPei and C.Chien, Low power TDMA in Large Wireless Sensor Networks, Military Communications Conference, Communications for Network-Centric Operations:Creating the Information Force,2001,1:28-31.
[18]Woo, D.Culler, A transmission control scheme for media access in sensor networks, Proceedings of the ACM MobiCom 2001,221-235.
[19]L. Qing, Q. Zhu, and M. Wang,"Design of a Distributed Energy-efficient Clustering Algorithm for Heterogeneous Wireless Sensor Networks,"Computer Communications, 2006, Vol.29, Issue 12, pp.2230-2237
[20]S.Capkun, J.P.Hubaux, and Levente Buttyan, Mobility Helps Security in Ad Hoc Networks, Proceedings of MobiHOC,2003,46-56.
[21]李田,史浩山,杨俊刚.无线传感器网络LEACH协议成簇算法研究[J].传感技术学报,2010,(08)：1158-1162.
[22]A. Manjeshwar and D. P. Agrawal, "TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks," Proceedings of the 1st International Workshop on Parallel and Distribute d Computing Issues in Wireless Networks and Mobile Computing,2001, pp.2009-2015.
[23]S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin and A. O. Fapojuwo,"A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks,"IEEE Radio Communications Magazine,2005, Vol.43, Issue 3, pp.8-13.
[24]J. Qiangfeng and D. Manivannan, "Routing Protocols for Sensor Networks," Proceedings of the Consumer Communications and Networking Conference,2004, pp.93-98.
[25]M. G Rezaie, V. S. Mansouri and M. Mani, "Critical Area Attention in Traffic Aware Dynamic Node Scheduling for Low Power Sensor Networks," Proceedings of the Wireless Communications and Networking Conference,2005, Vol.4, pp.1933-1938.
[26]Philip Levis and David Culler, Mate:a Tiny Virtual Machine for Sensor Networks, Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X), ACM Press,2002,85-95.
[27]R. Shah and J. Rabaey, " Energy Aware Routing for Low Energy Ad Hoc Sensor Networks," Proceedings of the IEEE Wireless Communications and Networking Conference,2002, Vol. 1, pp.350-355
[28]张源.一种TEEN协议的节能型改进算法[J].现代计算机(专业版),2009,(05)：61-64.
[29]D. Braginsky and D. Estrin, "Rumor Routing Algorithm for Sensor Networks," Proceedings of the First Workshop on Sensor Networks and Applications,2002, pp.22-31
[30]段磊.无线传感器网络基于梯度的分级簇算法研究[D].[硕士学位论文].郑州：郑州大学,2009
[31]阎新芳,段磊,李腾.无线传感器网络中基于梯度的拓扑控制算法[J].计算机工程与应用,2011,(02)：95-98.
[32]A.Wang, W. B. Heinzelmen, A. Sinha and A. P. Chanderkasan, Energy-scalable protocols for battery-operated microsensor networks, Journal of VLSI Signal Processing,2001,29: 223-237.
[33]阎新芳,孙雨耕,赵承利,无线传感器网络中基于能量的分级簇算法[J],天津大学学报,2005,38(12)：1106-1110
[34]Perillo M, Zhao C, Heinzelman W.On the problem of unbalanced load distribution in wireless sensor networks[C], Globe Com Workshops 2004.[S.1.]:IEEE,2004:74-79.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |