无线传感器网络低能耗路由算法研究
|
摘要
无线传感器网络具有广阔的应用前景。本文主要研究无线传感器网络路由协议。通过分析和比较已有路由算法和降低能耗策略,改进或提出了新的路由算法。
1)对低功耗自适应分层路由算法(LEACH)进行改进。改进后的算法基于节点的位置信息,将网络覆盖范围划分为若干区域,根据区域内节点剩余能量定期按需更新簇头,减少和均衡每个传感器耗能。
2)讨论了一种基于二叉树的低能耗路由算法。该算法根据各节点的最多剩余能量在感知区域内建立以Sink节点为根的源路由树。并对节点拥有的孩子数做一个软限制来优化算法,从而降低等待时间,均衡能耗,提高网络生存时间。
通过分析和仿真实验证明改进的算法在系统能量消耗、网络生存生存时间方面得到了改善。
Wireless sensor network is a new research area of science and technology and has a wide application. According to analyze some routing protocols and the techniques to reduce energy consumption, new algorithms are proposed.
1) A Location Based Cluster Routing proposed. Firstly the network covering is divided into some areas based on nodes location information, and then the cluster head is rotated periodically if necessary according to the nodes’residual energy.
2) A tree-based energy-efficient routing algorithm is discussed. According to maximum residual energy of nodes, a tree whose root is the sink node is set up. And to optimize the algorithm, we put a soft limit on the maximum number of children a node can have in a tree.
Analysis and simulation results show that the algorithms can performance well.
1)对低功耗自适应分层路由算法(LEACH)进行改进。改进后的算法基于节点的位置信息,将网络覆盖范围划分为若干区域,根据区域内节点剩余能量定期按需更新簇头,减少和均衡每个传感器耗能。
2)讨论了一种基于二叉树的低能耗路由算法。该算法根据各节点的最多剩余能量在感知区域内建立以Sink节点为根的源路由树。并对节点拥有的孩子数做一个软限制来优化算法,从而降低等待时间,均衡能耗,提高网络生存时间。
通过分析和仿真实验证明改进的算法在系统能量消耗、网络生存生存时间方面得到了改善。
Wireless sensor network is a new research area of science and technology and has a wide application. According to analyze some routing protocols and the techniques to reduce energy consumption, new algorithms are proposed.
1) A Location Based Cluster Routing proposed. Firstly the network covering is divided into some areas based on nodes location information, and then the cluster head is rotated periodically if necessary according to the nodes’residual energy.
2) A tree-based energy-efficient routing algorithm is discussed. According to maximum residual energy of nodes, a tree whose root is the sink node is set up. And to optimize the algorithm, we put a soft limit on the maximum number of children a node can have in a tree.
Analysis and simulation results show that the algorithms can performance well.
引文
[1] Zheng Guping, Zhou Yu. An Energy-aware Cluster Protocol for Wireless Sensor Networks.The Second International Conference on Innovative Computing, Information and Control. IEEE,kumamoto, Japan. Sep. 5-7, 2007.
[2] Zheng Guping, Zhou Yu. A Tree-based Energy-efficient Routing Algorithm for Wireless Sensor Networks.The 2007 International Conference on Information Computing and Automation.IEEE, Cheng Du.Dec.20-22.2007.
[3] 海斌、曾鹏等,智能无线传感器网络系统,科学出版社,2006 年 1 月第一版。
[4] BULTK BURSTEIN,CHANGD.Low power systems for wireless micro-sensors. International Symposium of Low Power Electronics and Design Monterey,CA,1996.. 16~27.
[5] ZHONG L,SHAH R,GUO C.An ultra-low power and distributed access protocol for broadband wireless sensor networks.IEEE Broadband Wireless Summit.Las Vegas,USA,2001.
[6] WO A, Culler D.A transmission control scheme for media access in sensor networks. Proceedings of the Seventh Annual International Conference on Mobile omputing and Networks.Rome,Italy,2001.221~235.
[7] NANDAGOPAL KIM, L GAO X.Achieving MAC layer fairness in wireless packet networks.Proceedings of the Sixth Annual International Conference on Mobile Computing and Networks.Boston,USA,2000.87~98.
[8] Elson J,Estrin D. Time synchronization for wireless sensor network.In: Proceedings of the 15th Parallel and Distributed Processing Symposium. San Francisco: IEEE Computer Society.2001.1965 ~1970.
[9] Baruch Awerbuch, David Holmer, Herbert Rubens. The Pulse Protocol: Routing and Power Saving Sensor Network.IEEE Military Communications Conference. Nov 2004. Volume 2.662 ~667.
[10] Xiaobing Hou, David Tippe, Shuju Wu.Traffic-aware Gossip-based Energy Conservation for Wireless Ad Hocand Sensor Network Routing.IEEE CCNC 2006 proceedings. 2006Volume 1, Issue: 8.341 ~345.
[11]Shibo Wu, K. Selcuk Candan.Power-aware single- and multipath geographic routing in sensor networks.Ad Hoc Networks.2006. 1794~1822.
[12]S. Upadhyayula, S.K.S. Gupta .Spanning tree based algorithms for low latency and e nergy efficient data aggregation enhanced converge cast (DAC) in wireless sensor networks.Ad Hoc Networks.2006. 74~1288.
[13]Dandan Liu , Xiaodong Hu ,Xiaohua Jia. Energy efficient information dissemination protocols by negotiation for wireless sensor networks. Computer Communications 29(2006) July 2006, Volume 29, Issue 11.2136~2149.
[14]I. Akyildiz, W. Su, Y. Sankarasubramaniam. A survey on Sensor Networks. IEEE Communications Magazine, August 2002.vol. 40, Issue: 8. 102~114
[15]Shijin Dai, Xiaorong Jing, Lemin Li. Research and analysis on routing protocols for wireless sensor networks. NSFC and RGC of HK (60218002) May 2005.Volume 1. 407 ~411.
[16]B. Karp, H.T. Hung.GPSR greedy perimeter stateless routing for wireless networks.The Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Boston, MA, August 2000. 566~577.
[17] Hongwei Du , Xiaodong Hu , Xiaohua Jia,Energy efficient routing and scheduling for real-time data aggregation in WSNs,Computer Communications,November 2006, Volume 29, Issue 17, 8 .3527~3535.
[18]Yu Hea, Cauligi S, Raghavendra.Building programmable routing service for sensor networks, Computer Communications 28 (2005).Volume 28, Issue 6.664-675.
[19] Basagni S. Distributed clustering for Ad hoc networks. In:Proceedings of International Symposium on Parallel Architectures, Algorithms and Network.Australia:1999.310~315.
[20]YounisO,Fahmy S. Distributed clustering for scalable,long-lived sensor networks. In: MOBICOM 2003.San Diego.USA :2003.
[21] Wendi B. Heinzelman, Anantha P. Chandrakasan, and Hari Balakrishnan. An Application-Specific Protocol Architecture forWireless Microsensor Networks. IEEE/IEE Electronic Library database .Oct.2002.
[22] Peng-Jun Wan, Alzoubi K. M. Frieder O. Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks.INFOCOM, June 2002, 157 -164.
[23] Gandham S R, Dawande M,Prakash R, et a1.Energy efficient chemes for wireless sensor networks with multiple mobile base stations.In:GLOBECOM 2003.IEEE Corn. munications Society.San Francisco,USA:2003.377~381.
[24] 唐勇﹑周明天﹑张欣. 无线传感器网络路由协议研究进展. 软件学报. March 2006.Vol.17,No.3. 410~421.
[25] 付昀﹑郑南宁﹑徐维朴. NS-2网络仿真器中动态路由算法的动画仿真研究. 系统仿真学报. June 2003, Vol.15,No.6. 863~868.
[26] 臧传真﹑范玉顺. 无线传感器网络中信息获取关键问题的研究..传感器技术. Vol.24,No.9.2005. 23~29.
[27] 梁英﹑曾鹏﹑于海斌. 无线传感器网络中一种能量自适应的簇首选择机制. 信息与控制.Apr.2006.Vol.35No.2. 141~146.
[28] 孙雨耕﹑张 静等. 无线自组传感器网络. 传感技术学报. June 2004.Vol.11,No.2. 331~348.
[29] 彭刚﹑曹元大等.无线传感器网络的数据汇聚机制.计算机工程.March 2006. Vol.32,No.6. 115~117.
[30] 滑楠﹑史浩山等.无线传感器网络簇间路由算法研究.计算机工程与应用.2005. Vol.12,No.6. 125~129.
[31] X. Cheng, B. Narahari, R. Simha, M. Cheng, D. Liu. Strong minimum energy topology in wireless sensor networks: Np-completeness and heuristics, Mobile Computing 2 (3) (2003) 248~256.
[32] S. Datta, I. Stojmenovic, J. Wu. Internal node and shortcut based routing with guaranteed delivery in wireless networks. Cluster Computing 5 (2) (2002) 169~178.
[33] L.M. Feeney. An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks.Mobile Networks and Applications 6 (3) (2001) 239~249.
[34] B. Hohlt, L. Doherty, E. Brewer.Flexible power scheduling for sensor networks. In: IPSN, 2004.205~214.
[35] D.B. Johnson, D.A. Maltz, Dynamic source routing in ad hoc wireless networks, in: Mobile Computing, 1996.153~181.
[36] S. Lindsey, C. Raghavendra. PEGASIS: Power-Efficient Gathering in Sensor Information Systems.IEEE Aerospace Conference Proceedings, 2002, Vol. 3, 9-16 1125~1130.
[37] Sokwoo Rhee, Deva Seetharam, Sheng Liu, Ningya Wang, Jason Xiao. I-Beans: An Ultra-low Power Wireless Sensor Network.
[38] Bhaskar Krishnamachari, Deborah Estrin, Stephen Wicke.The Impact of Data Aggregation in Wireless Sensor Networks.Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCSW 2002).575~578.
[39] 郑增威. 基于能量高效的传感器网络路由算法研究.浙江大学博士学位论文.2005年.
[40] 李宝强. 面向无线传感器网络的低能耗关键技术研究.西北工业大学论文.2005年.
[41] 阎新芳﹑孙雨耕﹑赵承利.无线传感器网络中基于能量的分级簇算法.天津大学学报.Dec.2005.Vol.38,No.12.106~1110.
[42] 梁英﹑于海斌等.应用PSO优化基于分簇的无线传感器网络路由协议.控制与决策. Apr.2006.Vo1.21,No.4. 454~461.
[43] 董婷﹑林亚平等.传感器网络中基于簇的自适应路由算法.计算机应用.May 2006.Vol.26.No.5. 1148~1151.
[44] F. Bennett, D. Clarke, J. Evans, A. Hopper, A. Jones, D. Leask. Piconet: embedded mobile networking.IEEE Personal Communications 4 (5) (1997) 8~15.
[45] J.H. Chang, L. Tassiulas. Energy conserving routing in wireless ad hoc networks, in: INFOCOM, 2000.22~31.
[2] Zheng Guping, Zhou Yu. A Tree-based Energy-efficient Routing Algorithm for Wireless Sensor Networks.The 2007 International Conference on Information Computing and Automation.IEEE, Cheng Du.Dec.20-22.2007.
[3] 海斌、曾鹏等,智能无线传感器网络系统,科学出版社,2006 年 1 月第一版。
[4] BULTK BURSTEIN,CHANGD.Low power systems for wireless micro-sensors. International Symposium of Low Power Electronics and Design Monterey,CA,1996.. 16~27.
[5] ZHONG L,SHAH R,GUO C.An ultra-low power and distributed access protocol for broadband wireless sensor networks.IEEE Broadband Wireless Summit.Las Vegas,USA,2001.
[6] WO A, Culler D.A transmission control scheme for media access in sensor networks. Proceedings of the Seventh Annual International Conference on Mobile omputing and Networks.Rome,Italy,2001.221~235.
[7] NANDAGOPAL KIM, L GAO X.Achieving MAC layer fairness in wireless packet networks.Proceedings of the Sixth Annual International Conference on Mobile Computing and Networks.Boston,USA,2000.87~98.
[8] Elson J,Estrin D. Time synchronization for wireless sensor network.In: Proceedings of the 15th Parallel and Distributed Processing Symposium. San Francisco: IEEE Computer Society.2001.1965 ~1970.
[9] Baruch Awerbuch, David Holmer, Herbert Rubens. The Pulse Protocol: Routing and Power Saving Sensor Network.IEEE Military Communications Conference. Nov 2004. Volume 2.662 ~667.
[10] Xiaobing Hou, David Tippe, Shuju Wu.Traffic-aware Gossip-based Energy Conservation for Wireless Ad Hocand Sensor Network Routing.IEEE CCNC 2006 proceedings. 2006Volume 1, Issue: 8.341 ~345.
[11]Shibo Wu, K. Selcuk Candan.Power-aware single- and multipath geographic routing in sensor networks.Ad Hoc Networks.2006. 1794~1822.
[12]S. Upadhyayula, S.K.S. Gupta .Spanning tree based algorithms for low latency and e nergy efficient data aggregation enhanced converge cast (DAC) in wireless sensor networks.Ad Hoc Networks.2006. 74~1288.
[13]Dandan Liu , Xiaodong Hu ,Xiaohua Jia. Energy efficient information dissemination protocols by negotiation for wireless sensor networks. Computer Communications 29(2006) July 2006, Volume 29, Issue 11.2136~2149.
[14]I. Akyildiz, W. Su, Y. Sankarasubramaniam. A survey on Sensor Networks. IEEE Communications Magazine, August 2002.vol. 40, Issue: 8. 102~114
[15]Shijin Dai, Xiaorong Jing, Lemin Li. Research and analysis on routing protocols for wireless sensor networks. NSFC and RGC of HK (60218002) May 2005.Volume 1. 407 ~411.
[16]B. Karp, H.T. Hung.GPSR greedy perimeter stateless routing for wireless networks.The Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Boston, MA, August 2000. 566~577.
[17] Hongwei Du , Xiaodong Hu , Xiaohua Jia,Energy efficient routing and scheduling for real-time data aggregation in WSNs,Computer Communications,November 2006, Volume 29, Issue 17, 8 .3527~3535.
[18]Yu Hea, Cauligi S, Raghavendra.Building programmable routing service for sensor networks, Computer Communications 28 (2005).Volume 28, Issue 6.664-675.
[19] Basagni S. Distributed clustering for Ad hoc networks. In:Proceedings of International Symposium on Parallel Architectures, Algorithms and Network.Australia:1999.310~315.
[20]YounisO,Fahmy S. Distributed clustering for scalable,long-lived sensor networks. In: MOBICOM 2003.San Diego.USA :2003.
[21] Wendi B. Heinzelman, Anantha P. Chandrakasan, and Hari Balakrishnan. An Application-Specific Protocol Architecture forWireless Microsensor Networks. IEEE/IEE Electronic Library database .Oct.2002.
[22] Peng-Jun Wan, Alzoubi K. M. Frieder O. Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks.INFOCOM, June 2002, 157 -164.
[23] Gandham S R, Dawande M,Prakash R, et a1.Energy efficient chemes for wireless sensor networks with multiple mobile base stations.In:GLOBECOM 2003.IEEE Corn. munications Society.San Francisco,USA:2003.377~381.
[24] 唐勇﹑周明天﹑张欣. 无线传感器网络路由协议研究进展. 软件学报. March 2006.Vol.17,No.3. 410~421.
[25] 付昀﹑郑南宁﹑徐维朴. NS-2网络仿真器中动态路由算法的动画仿真研究. 系统仿真学报. June 2003, Vol.15,No.6. 863~868.
[26] 臧传真﹑范玉顺. 无线传感器网络中信息获取关键问题的研究..传感器技术. Vol.24,No.9.2005. 23~29.
[27] 梁英﹑曾鹏﹑于海斌. 无线传感器网络中一种能量自适应的簇首选择机制. 信息与控制.Apr.2006.Vol.35No.2. 141~146.
[28] 孙雨耕﹑张 静等. 无线自组传感器网络. 传感技术学报. June 2004.Vol.11,No.2. 331~348.
[29] 彭刚﹑曹元大等.无线传感器网络的数据汇聚机制.计算机工程.March 2006. Vol.32,No.6. 115~117.
[30] 滑楠﹑史浩山等.无线传感器网络簇间路由算法研究.计算机工程与应用.2005. Vol.12,No.6. 125~129.
[31] X. Cheng, B. Narahari, R. Simha, M. Cheng, D. Liu. Strong minimum energy topology in wireless sensor networks: Np-completeness and heuristics, Mobile Computing 2 (3) (2003) 248~256.
[32] S. Datta, I. Stojmenovic, J. Wu. Internal node and shortcut based routing with guaranteed delivery in wireless networks. Cluster Computing 5 (2) (2002) 169~178.
[33] L.M. Feeney. An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks.Mobile Networks and Applications 6 (3) (2001) 239~249.
[34] B. Hohlt, L. Doherty, E. Brewer.Flexible power scheduling for sensor networks. In: IPSN, 2004.205~214.
[35] D.B. Johnson, D.A. Maltz, Dynamic source routing in ad hoc wireless networks, in: Mobile Computing, 1996.153~181.
[36] S. Lindsey, C. Raghavendra. PEGASIS: Power-Efficient Gathering in Sensor Information Systems.IEEE Aerospace Conference Proceedings, 2002, Vol. 3, 9-16 1125~1130.
[37] Sokwoo Rhee, Deva Seetharam, Sheng Liu, Ningya Wang, Jason Xiao. I-Beans: An Ultra-low Power Wireless Sensor Network.
[38] Bhaskar Krishnamachari, Deborah Estrin, Stephen Wicke.The Impact of Data Aggregation in Wireless Sensor Networks.Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCSW 2002).575~578.
[39] 郑增威. 基于能量高效的传感器网络路由算法研究.浙江大学博士学位论文.2005年.
[40] 李宝强. 面向无线传感器网络的低能耗关键技术研究.西北工业大学论文.2005年.
[41] 阎新芳﹑孙雨耕﹑赵承利.无线传感器网络中基于能量的分级簇算法.天津大学学报.Dec.2005.Vol.38,No.12.106~1110.
[42] 梁英﹑于海斌等.应用PSO优化基于分簇的无线传感器网络路由协议.控制与决策. Apr.2006.Vo1.21,No.4. 454~461.
[43] 董婷﹑林亚平等.传感器网络中基于簇的自适应路由算法.计算机应用.May 2006.Vol.26.No.5. 1148~1151.
[44] F. Bennett, D. Clarke, J. Evans, A. Hopper, A. Jones, D. Leask. Piconet: embedded mobile networking.IEEE Personal Communications 4 (5) (1997) 8~15.
[45] J.H. Chang, L. Tassiulas. Energy conserving routing in wireless ad hoc networks, in: INFOCOM, 2000.22~31.