基于负载均衡的无线传感器网络路由协议研究
摘要
无线传感器网络是本世纪IT领域的一个研究热点。它提高了人们对信息的获取能力,因为它可以为人类提供最直接、最有效、最真实的客观物理信息,鉴于此,它已经引起了军事领域、民用领域以及学术界的广泛关注,展望未来,无线传感器网络有着非常广阔的市场应用前景。
无线传感器网络由众多传感器节点组成,节点的处理能力、存储能力和通信能力都是有限的,而且这些节点一般分布在比较恶劣的环境之中,所以能量的补给或者节点的更换都受到很大的限制,这些问题带来了无线传感器网络一些固有的缺陷,如节点的能量有限、通讯介质开放、带宽固定等等。本文按照无线传感器网络中路由协议的发展顺序,对其中比较典型的路由协议做了分析,并总结了各自的优缺点。在此基础上,针对之前协议中能量利用不够充分的问题,本文提出了基于蚁群优化的负载均衡的动态路由算法-BEACO。
这种能量负载均衡的动态路由算法,主要有两处改进,其一是在选择下一跳节点时不止参考路径上Pheromone素的浓度,同时参考下一跳节点的剩余能量,即将下一跳的选择抽象成为基于最短路径和最小费用流的组合规划问题,其二,Pheromone素的更新以及挥发都参考了下一跳的能量,能量较少的节点被选择成为下一跳的可能性就会变小,这样就能保证该节点的存活,即网络的完整性,从而延长生命周期。本文采用ns2仿真工具进行实验,并与传统蚁群算法和其他参考能量的蚁群算法EEABR进行了比较,实验证明,使用该方法能有效的利用网络中各节点的能量,明显的延长网络的生命周期。并且该方法对网络规模没有限制,适用性更广
WSN (Wireless Sensor Network) is a hot topic in IT field during this century. It improves our ability to obtain the information, because it can provide the most direct, most effective and most objective physical information for mankind. In view of this, WSN has already got the widespread attention in military field, civil domain as well as academic field. Looking forward to the future, the wireless sensor network has the very broad prospect on market applications.
Wireless Sensor Network consists of many sensor nodes whose capabilities, such as processing, storage and communications, are limited. The sensor nodes generally located in relatively harsh environment, so it is impossible to supply energy or substitute node for the network. The above problems have brought some inherent defects on wireless sensor networks, such as the limited energy supply, opened communication medium, fixed bandwidth and so on. According with the development of routing protocols in wireless sensor network, this paper analyzes some typical routing protocols and summarizes their advantages and defects.In summary, the utilization of energy is not sufficient. To solve this problem, this paper puts forward a load balancing dynamic routing algorithm based on ant colony optimization, BEACO.
There are two improvements on this load balancing dynamic routing algorithm. The first improvement is that the choice of next hop node not only refers to the Pheromone on the path, but also refers to the residual energy of the next hop node, that is to view the choice of next hop as a combination planning issues based on the shortest path and minimum cost. The second improvement is that the update and volatilization of Pheromone are both reference to the energy of next hop node, that is to say the node with less energy will have smaller possibility to be selected as the next hop.This algorithm can guarantee the survival of the node with little energy, thus extending the life cycle of the network. In this paper, the simulation environment on the experiments is ns2.Compared with the traditional ant colony algorithm and other ant colony algorithm referred to energy, EEABR, the BEACO can effectively use the energy of each node in the network, and prolong the life cycle of the network. The algorithm BEACO does not limit the scale of the network, so it has broader applicability than other algorithms.
无线传感器网络由众多传感器节点组成,节点的处理能力、存储能力和通信能力都是有限的,而且这些节点一般分布在比较恶劣的环境之中,所以能量的补给或者节点的更换都受到很大的限制,这些问题带来了无线传感器网络一些固有的缺陷,如节点的能量有限、通讯介质开放、带宽固定等等。本文按照无线传感器网络中路由协议的发展顺序,对其中比较典型的路由协议做了分析,并总结了各自的优缺点。在此基础上,针对之前协议中能量利用不够充分的问题,本文提出了基于蚁群优化的负载均衡的动态路由算法-BEACO。
这种能量负载均衡的动态路由算法,主要有两处改进,其一是在选择下一跳节点时不止参考路径上Pheromone素的浓度,同时参考下一跳节点的剩余能量,即将下一跳的选择抽象成为基于最短路径和最小费用流的组合规划问题,其二,Pheromone素的更新以及挥发都参考了下一跳的能量,能量较少的节点被选择成为下一跳的可能性就会变小,这样就能保证该节点的存活,即网络的完整性,从而延长生命周期。本文采用ns2仿真工具进行实验,并与传统蚁群算法和其他参考能量的蚁群算法EEABR进行了比较,实验证明,使用该方法能有效的利用网络中各节点的能量,明显的延长网络的生命周期。并且该方法对网络规模没有限制,适用性更广
WSN (Wireless Sensor Network) is a hot topic in IT field during this century. It improves our ability to obtain the information, because it can provide the most direct, most effective and most objective physical information for mankind. In view of this, WSN has already got the widespread attention in military field, civil domain as well as academic field. Looking forward to the future, the wireless sensor network has the very broad prospect on market applications.
Wireless Sensor Network consists of many sensor nodes whose capabilities, such as processing, storage and communications, are limited. The sensor nodes generally located in relatively harsh environment, so it is impossible to supply energy or substitute node for the network. The above problems have brought some inherent defects on wireless sensor networks, such as the limited energy supply, opened communication medium, fixed bandwidth and so on. According with the development of routing protocols in wireless sensor network, this paper analyzes some typical routing protocols and summarizes their advantages and defects.In summary, the utilization of energy is not sufficient. To solve this problem, this paper puts forward a load balancing dynamic routing algorithm based on ant colony optimization, BEACO.
There are two improvements on this load balancing dynamic routing algorithm. The first improvement is that the choice of next hop node not only refers to the Pheromone on the path, but also refers to the residual energy of the next hop node, that is to view the choice of next hop as a combination planning issues based on the shortest path and minimum cost. The second improvement is that the update and volatilization of Pheromone are both reference to the energy of next hop node, that is to say the node with less energy will have smaller possibility to be selected as the next hop.This algorithm can guarantee the survival of the node with little energy, thus extending the life cycle of the network. In this paper, the simulation environment on the experiments is ns2.Compared with the traditional ant colony algorithm and other ant colony algorithm referred to energy, EEABR, the BEACO can effectively use the energy of each node in the network, and prolong the life cycle of the network. The algorithm BEACO does not limit the scale of the network, so it has broader applicability than other algorithms.
引文
[1]孙利民,李建中,陈渝等.无线传感器网络[M].北京：清华大学出版社,2005.
[2]O. Younis,S. Fahmy. Distributed Clustering in Ad-Hoc Sensor Networks:A Hybrid, Energy-Efficient Approach[C].Proceedings of the IEEE INFOCOM, Hong Kong,2004:629-640.
[3]于宏毅,李鸥,张效义等.无线传感器网络理论、技术与实现[M].北京：国防工业出版社,2008.
[4]Liao W. H,Kao Y, Fan C.M. Data aggregation in wireless sensor networks using ant colony algorithm[J].J. Netw. Comput. Appl,2008,31(4):387-401.
[5]Misra R,Mandal C. Ant-aggregation:ant colony algorithm for optimal data aggregation in wireless sensor networks [C].International Conference on Wireless and Optical Communications Networks, Bangalore,2006:1-5.
[6]Manjeshwar A,Grawal DP. TEEN:A protocol for enhanced efficiency in wireless sensor networks[R].San Francisco:IEEE Computer Society,2001.
[7]王建明.发射功率可变的无线传感器网络能量级别选取[J].计算机工程,2009,35(13)：108-110.
[8]Anantha Chandrakasan, Anantha Ch, Rajeevan Amirtharajah, et al.Design considerations for distributed microsensor systems[C].Proceedings of the IEEE Custom Integrated Circuits Conf.,San Diego, CA, USA,1999:279-286.
[9]Edgar H,Callaway Jr. Wireless Sensor Networks Architectures and Protocols [M]. Auerbach Publications,2003.
[10]C.B.Williams and R. B. Yates, Analysis of a micro-electric generator for Microsystems[C],Proceedings of 8th Int.Conf. on Solid-State Sensors and Actuators and Euro sensors IX,会址,1995:369-372.
[11]Fan K. W, Liu S,Sinha P. On the potential of Structure-free Data Aggregation in Sensor Networks[C].Proceedings of the IEEE International Conference on Computer Communications,Barcelona, Spain:INFOCOM,2006:1-12
[12]Al-Karaki JN, Ul-Mustafa R, Kamal AE.Data aggregation in wireless sensor networks-exact and approximate algorithms[R].International Workshop on High-Performance Switching and Routing,2004:241-245.
[13]Krishnamachari B, Estrin D,Wicker S.The impact of data aggregation in wireless sensor networks[C].International Conference on Distributed Computing Systems Workshops(ICDCSW),Vienna, Austria,2002:575-578.
[14]Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion:A scalable and robust communication paradigm for sensor networks[C].Proceedings of 6th 'Annual Int'1 Conf on Mobile Computing and Networks(MobiCOM 2000),Boston, MA,2000:56-67.
[15]Shah R C, Rabaey J M. Energy aware routing for low energy ad hoc sensor network[C]. Proceedings of IEEE Wireless Communications and Networking Conference (WCNC'02),IEEE, 2002:Volume 1,17-21.
[16]Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-Efficient communication protocol for wireless microsensor networks[C].IEEE Computer Society,Hawaii,2000:3005-3014.
[17]Younis O,Fahmy S.Heed:A hybrid, energy-efficient,distributed clustering approach for ad-hoc sensor networks[J].IEEE Trans. On Mobile Computing,2004,3(4):660-669.
[18]Sanjit Biswas,Robert Morris.ExOR:Opportunistic Multi-Hop Routing for Wireless Networks[C].SIGCOMM'05,Philadelphia, Pennsylvania, USA,2005:133-143
[19]吴启迪,汪镭.智能蚁群算法及应用[M].上海：上海科技教育出版社,2004.
[20]Jie Lian, Sagar Naik,Gordon B. Agnew. Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J].International Journal of Distributed Sensor Networks,2006,2:121-145.
[21]Tiago Camilo, Carlos Carreto, Jorge Sa Silva, et al.An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks[C].ANTS 2006, LNCS 4150, Berlin Heidelberg, 2006:49-59.
[22]Zhu Xiangbin. Pheromone Based Energy Aware Directed Diffusion Algorithm for Wireless Sensor Network[C].ICIC2007,LNCS4681,Berlin Heidelberg,2007:283-191.
[23]Ayan Acharya, Anand Seetharam, Abhishek Bhattacharyya. Balancing Energy Dissipation in Data Gathering Wireless Sensor Networks Using Ant Colony Optimization[C].ICDCN 2009, LNCS 5408,Berlin Heidelberg,2009:437-443.
[24]刘娅.无线传感器网络能量模型及其仿真研究[D].成都：电子科技大学,2008.
[25]Masoud Daneshtalab, Ali Afzali Kusha, Ashkan Sobhani,Zainanabedin Navabi,Mohammad D.Mottaghi,and Omid Fatemi.Ant Colony Based Routing Architecture for Minimizing Hot Spots in NOCs[C].SBCCI'06,proceedings of the 19th annual symposium on Integrated circuits and systems design. Brazil,2006:56-61.
[26]Chen G, Guo T-D, Yang W-G, et al.An improved ant-based routing protocol in wireless sensor networks[C].International Conference on Collaborative Computing:Networking, Applications and Worksharing (CollaborateCom),Atlanta, GA,USA,2006:1-7.
[27]Al-Jarrah O, Sa'deh W. Enhanced AODV routing protocol for mobile ad hoc networks[C]. 16th international conference on computer theory and applications(ICCTA),New Delhi,2006: 1-5.
[28]王佳英.基于蚁群优化的无线传感器网络路由协议研究[D].大连：大连理工大学电信学院,2009.
[2]O. Younis,S. Fahmy. Distributed Clustering in Ad-Hoc Sensor Networks:A Hybrid, Energy-Efficient Approach[C].Proceedings of the IEEE INFOCOM, Hong Kong,2004:629-640.
[3]于宏毅,李鸥,张效义等.无线传感器网络理论、技术与实现[M].北京：国防工业出版社,2008.
[4]Liao W. H,Kao Y, Fan C.M. Data aggregation in wireless sensor networks using ant colony algorithm[J].J. Netw. Comput. Appl,2008,31(4):387-401.
[5]Misra R,Mandal C. Ant-aggregation:ant colony algorithm for optimal data aggregation in wireless sensor networks [C].International Conference on Wireless and Optical Communications Networks, Bangalore,2006:1-5.
[6]Manjeshwar A,Grawal DP. TEEN:A protocol for enhanced efficiency in wireless sensor networks[R].San Francisco:IEEE Computer Society,2001.
[7]王建明.发射功率可变的无线传感器网络能量级别选取[J].计算机工程,2009,35(13)：108-110.
[8]Anantha Chandrakasan, Anantha Ch, Rajeevan Amirtharajah, et al.Design considerations for distributed microsensor systems[C].Proceedings of the IEEE Custom Integrated Circuits Conf.,San Diego, CA, USA,1999:279-286.
[9]Edgar H,Callaway Jr. Wireless Sensor Networks Architectures and Protocols [M]. Auerbach Publications,2003.
[10]C.B.Williams and R. B. Yates, Analysis of a micro-electric generator for Microsystems[C],Proceedings of 8th Int.Conf. on Solid-State Sensors and Actuators and Euro sensors IX,会址,1995:369-372.
[11]Fan K. W, Liu S,Sinha P. On the potential of Structure-free Data Aggregation in Sensor Networks[C].Proceedings of the IEEE International Conference on Computer Communications,Barcelona, Spain:INFOCOM,2006:1-12
[12]Al-Karaki JN, Ul-Mustafa R, Kamal AE.Data aggregation in wireless sensor networks-exact and approximate algorithms[R].International Workshop on High-Performance Switching and Routing,2004:241-245.
[13]Krishnamachari B, Estrin D,Wicker S.The impact of data aggregation in wireless sensor networks[C].International Conference on Distributed Computing Systems Workshops(ICDCSW),Vienna, Austria,2002:575-578.
[14]Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion:A scalable and robust communication paradigm for sensor networks[C].Proceedings of 6th 'Annual Int'1 Conf on Mobile Computing and Networks(MobiCOM 2000),Boston, MA,2000:56-67.
[15]Shah R C, Rabaey J M. Energy aware routing for low energy ad hoc sensor network[C]. Proceedings of IEEE Wireless Communications and Networking Conference (WCNC'02),IEEE, 2002:Volume 1,17-21.
[16]Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-Efficient communication protocol for wireless microsensor networks[C].IEEE Computer Society,Hawaii,2000:3005-3014.
[17]Younis O,Fahmy S.Heed:A hybrid, energy-efficient,distributed clustering approach for ad-hoc sensor networks[J].IEEE Trans. On Mobile Computing,2004,3(4):660-669.
[18]Sanjit Biswas,Robert Morris.ExOR:Opportunistic Multi-Hop Routing for Wireless Networks[C].SIGCOMM'05,Philadelphia, Pennsylvania, USA,2005:133-143
[19]吴启迪,汪镭.智能蚁群算法及应用[M].上海：上海科技教育出版社,2004.
[20]Jie Lian, Sagar Naik,Gordon B. Agnew. Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J].International Journal of Distributed Sensor Networks,2006,2:121-145.
[21]Tiago Camilo, Carlos Carreto, Jorge Sa Silva, et al.An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks[C].ANTS 2006, LNCS 4150, Berlin Heidelberg, 2006:49-59.
[22]Zhu Xiangbin. Pheromone Based Energy Aware Directed Diffusion Algorithm for Wireless Sensor Network[C].ICIC2007,LNCS4681,Berlin Heidelberg,2007:283-191.
[23]Ayan Acharya, Anand Seetharam, Abhishek Bhattacharyya. Balancing Energy Dissipation in Data Gathering Wireless Sensor Networks Using Ant Colony Optimization[C].ICDCN 2009, LNCS 5408,Berlin Heidelberg,2009:437-443.
[24]刘娅.无线传感器网络能量模型及其仿真研究[D].成都：电子科技大学,2008.
[25]Masoud Daneshtalab, Ali Afzali Kusha, Ashkan Sobhani,Zainanabedin Navabi,Mohammad D.Mottaghi,and Omid Fatemi.Ant Colony Based Routing Architecture for Minimizing Hot Spots in NOCs[C].SBCCI'06,proceedings of the 19th annual symposium on Integrated circuits and systems design. Brazil,2006:56-61.
[26]Chen G, Guo T-D, Yang W-G, et al.An improved ant-based routing protocol in wireless sensor networks[C].International Conference on Collaborative Computing:Networking, Applications and Worksharing (CollaborateCom),Atlanta, GA,USA,2006:1-7.
[27]Al-Jarrah O, Sa'deh W. Enhanced AODV routing protocol for mobile ad hoc networks[C]. 16th international conference on computer theory and applications(ICCTA),New Delhi,2006: 1-5.
[28]王佳英.基于蚁群优化的无线传感器网络路由协议研究[D].大连：大连理工大学电信学院,2009.