基于蚁群算法的WSN路由算法研究
摘要
无线传感器网络(Wireless Sensor Network, WSN)是由部署在监测区域内大量的微型传感器节点,通过无线通信方式形成的一个多跳的自组织的网络系统。其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息,并发送给观察者。无线传感器网络是计算机科学技术的一个新的研究领域,具有非常广阔的应用前景,已经引起了学术界和工业界的高度重视。
路由技术是无线传感器网络的关键技术,也是影响网络整体性能的重要因素之一。由于无线传感器网络和其它的通信网路,包括无线Ad hoc网络相比,有着截然不同的特点,这就使得无线传感器网络的路由研究极具挑战性。近年来提出了不少专门针对无线传感器网络的路由协议,如泛洪法(Flooding)、信息协商传感器协议(SPIN)、定向扩散协议(DD)等。本文详细的研究了这几种路由协议,并在此基础上提出了基于蚁群优化算法的无线传感器网络路由算法。
该算法是由Sink节点在整个网络中定期的广播名为IMP(Interest Message Packet)的报文,向整个网络传送Sink节点所感兴趣的数据特征,并且建立和更新梯度场,形成和更新各条路径上的信息素。信息素的形成不仅要考虑节点之间的梯度,还要考虑节点的剩余能量。当某个节点发现符合要求的数据时,该节点成为源节点,并向Sink节点发送类似蚂蚁的数据包。节点在选择路由的时候,根据信息素的浓度来计算各相邻节点被选择作为下一跳的概率。也就是说,梯度大而且剩余能量多的相邻节点更有可能成为下一跳,因此数据包的发送不会总是沿着一条路径进行。这样,在尽量沿着梯度最大的路径发送数据的同时,尽可能平均的消耗各个节点的能量。同时,为了防止一些节点由于作为中间节点转发数据包过早死亡而导致这些节点所在的区域失去监控,在算法中还设置了节点的能量阈值,当节点的能量小于能量阈值时,就尽可能不要再承担转发数据的任务。通过对该路由算法的仿真,验证了该算法有效性,同时,仿真表明算法具有较小的平均延迟和平均能量消耗。
Wireless Sensor Networks(WSN)are composed of a large quantity of micro-sensors deployed in monitoring fields, they form the multi-hop and self-organizing network systems via wireless communicating. These sensors are used in cooperation with others to feel, collect, and process the information transmitted to the observer in monitoring fields. As a new researching area of computer science and technology, WSN, which will be used widely in the future, has aroused high attention in both academia and industrial circles.
Routing technique is not only the key technique in WSN, but also one of the most important factors affecting the performance of the network. Investigations about routing in WSN is very challenging due to several characteristics that distinguish it from contemporary communication and Ad hoc networks. In recent years, some specific routing protocols for WSN have emerged, such as Flooding, SPIN, DD, and so on. This paper makes detail investigations on those routing protocols. On the basis of assimilating the excellent ideas among them, an Ant-Colony-Based Routing Algorithms in WSN is proposed.
Ant-colony-based routing algorithm is that: Sink node regularly broadcasts IMP(Interest Message Packet) through the network in order to setup and update gradient field, at the same time, it can also form and update pheromone on each route, then transmit data which is interested by Sink node to the whole network. The gradient and remaining energy of the neighborhood are integrated into the computation of pheromone concentration. If a node has the right data to send, it becomes a source node which will transmit ant-like data packet to Sink. When choosing the route, the node will choose its next hop with probability, which is computed on the basis of pheromone concentration. And the data packet will not always be transmitted on the same route. Meanwhile, some nodes just live for a little while because of forwarding too many data packets from sources, and it leads to the loss of monitoring for some particular area. So an energy threshold for each node is set in the algorithm to prevent it. When the energy of some node is less than the energy threshold, it should avoid undertaking data-transmitting task. The simulation of Ant-Colony-Based Routing Algorithm proves itself to be effective, and simulation results also show that such algorithm is of less average delay and average dissipated energy
路由技术是无线传感器网络的关键技术,也是影响网络整体性能的重要因素之一。由于无线传感器网络和其它的通信网路,包括无线Ad hoc网络相比,有着截然不同的特点,这就使得无线传感器网络的路由研究极具挑战性。近年来提出了不少专门针对无线传感器网络的路由协议,如泛洪法(Flooding)、信息协商传感器协议(SPIN)、定向扩散协议(DD)等。本文详细的研究了这几种路由协议,并在此基础上提出了基于蚁群优化算法的无线传感器网络路由算法。
该算法是由Sink节点在整个网络中定期的广播名为IMP(Interest Message Packet)的报文,向整个网络传送Sink节点所感兴趣的数据特征,并且建立和更新梯度场,形成和更新各条路径上的信息素。信息素的形成不仅要考虑节点之间的梯度,还要考虑节点的剩余能量。当某个节点发现符合要求的数据时,该节点成为源节点,并向Sink节点发送类似蚂蚁的数据包。节点在选择路由的时候,根据信息素的浓度来计算各相邻节点被选择作为下一跳的概率。也就是说,梯度大而且剩余能量多的相邻节点更有可能成为下一跳,因此数据包的发送不会总是沿着一条路径进行。这样,在尽量沿着梯度最大的路径发送数据的同时,尽可能平均的消耗各个节点的能量。同时,为了防止一些节点由于作为中间节点转发数据包过早死亡而导致这些节点所在的区域失去监控,在算法中还设置了节点的能量阈值,当节点的能量小于能量阈值时,就尽可能不要再承担转发数据的任务。通过对该路由算法的仿真,验证了该算法有效性,同时,仿真表明算法具有较小的平均延迟和平均能量消耗。
Wireless Sensor Networks(WSN)are composed of a large quantity of micro-sensors deployed in monitoring fields, they form the multi-hop and self-organizing network systems via wireless communicating. These sensors are used in cooperation with others to feel, collect, and process the information transmitted to the observer in monitoring fields. As a new researching area of computer science and technology, WSN, which will be used widely in the future, has aroused high attention in both academia and industrial circles.
Routing technique is not only the key technique in WSN, but also one of the most important factors affecting the performance of the network. Investigations about routing in WSN is very challenging due to several characteristics that distinguish it from contemporary communication and Ad hoc networks. In recent years, some specific routing protocols for WSN have emerged, such as Flooding, SPIN, DD, and so on. This paper makes detail investigations on those routing protocols. On the basis of assimilating the excellent ideas among them, an Ant-Colony-Based Routing Algorithms in WSN is proposed.
Ant-colony-based routing algorithm is that: Sink node regularly broadcasts IMP(Interest Message Packet) through the network in order to setup and update gradient field, at the same time, it can also form and update pheromone on each route, then transmit data which is interested by Sink node to the whole network. The gradient and remaining energy of the neighborhood are integrated into the computation of pheromone concentration. If a node has the right data to send, it becomes a source node which will transmit ant-like data packet to Sink. When choosing the route, the node will choose its next hop with probability, which is computed on the basis of pheromone concentration. And the data packet will not always be transmitted on the same route. Meanwhile, some nodes just live for a little while because of forwarding too many data packets from sources, and it leads to the loss of monitoring for some particular area. So an energy threshold for each node is set in the algorithm to prevent it. When the energy of some node is less than the energy threshold, it should avoid undertaking data-transmitting task. The simulation of Ant-Colony-Based Routing Algorithm proves itself to be effective, and simulation results also show that such algorithm is of less average delay and average dissipated energy
引文
1.刘拥民,蒋新华,年晓红,等.无线传感器网络通信协议[J],微电子学与计算机,2007,24(10)：71-73.
2. Angelo Brayner, Aretusa Lopes, Diorgens Meira, et al. Toward adaptive query processing in wireless sensor networks [J], Signal Processing,2007,87(12):2911-2933.
3.孙利民,李建中,陈渝,等.无线传感器网络[M],北京：清华大学出版社,2005,24-25.
4.郑相全.无线自组网技术[M],北京：清华大学出版社,2004,15-17.
5. Akyildiz I.F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J], IEEE Communication Magazine,2002,40(8):102-114.
6. Azzedine Boukerche, Xin Fei. A coverage-preserving scheme for wireless sensor network with irregular sensing range[J], Ad Hoc Networks,2007,5(8):1303-1316.
7.代航阳,徐红兵.无线传感器网络安全综述[J],计算机应用研究,2007,23(7)：12-17.
8. Roberto Di Pietro,Luigi V. Mancini, Sushil Jajodia. Providing secrecy in key management protocols for large wireless sensors networks [J], Ad Hoc Networks,2003,1(4):455-468.
9. Yaoyi Mao, Frank R, Kschischang, et al. Factor graph approach to link loss monitoring in wireless sensor networks[J], IEEE Journal on Selected Areas in Communications,2005, 23(12):820-829.
10. Olivier Powell, Pierre Leone, Jose Rolim. Energy optimal data propagation in wireless sensor networks[J], Journal of Parallel and Distributed Computing,2007,67(3):302-317.
11. Woo A, Culler D E. A transmission control scheme for media access in sensor networks[A], Proceedings of the ACM MobiCom'01[C], Italy:ACM Press,2001, 221-235.
12. Haythem Bany Salameh, Tao Shu, Marwan Krunz. Adaptive cross-layer MAC design for improved energy-efficiency in multi-channel wireless sensor networks[J], Ad Hoc Networks,2007,5(6):844-854.
13. Ye Wei, Heidemann J, Estrin D. An energy-efficient MAC protocol for wireless sensor network[A], Proceedings of the INFORCOM'2002[C], San Francisco:IEEE Computer Society,2002,1567-1576.
14. Noury N, Herve T, Rialle V, et al. Monitoring behavior in home using a smart fall sensor[A], Proceedings of the IEEE-EMBS Special Topic Conference on Micro technologies in Medicine and Biology[C], Lyon:IEEE Computer Society,2000,607-610.
15.柯文德,李家兰.蚁群算法及其在TSP中的应用[J],茂名学院学报,2007,17(1)：53-55.
16. M.Duran Toksari. Ant colony optimization approach to estimate energy demand of Turkey[J], Energy Policy,2007,35(8):3984-3990.
17. Wei Yi, Arun Kumar. Ant colony optimization for disaster relief operations [J], Transportation Research Part E:Logistics and Transportation Review,2007,43(6): 660-672.
18.刘立东,蔡淮,赵旭.一类自适应蚁群算法的收敛性分析[J],计算机应用,2007,27(B06)：73-75.
19.方旺盛,肖琴.蚁群算法的收敛性分析及其在TSP上的求解[J],计算机与数字工程,2007,35(9)：46-48.
20. Botee H M, Bonabeau E. Evolving ant colony optimization[J], Advances in Complex Systems,1998,1(2):149-159.
21. Dorigo M, Caro G, Gambardella L M. Ant algorithms for discrete optimization[J], Artificial Life,1999,5(3),137-172.
22. Junhua Gu, Xiang Dan, Song Jie, et al. Solving QoS multicast routing problem based on heuristic ant algorithm[J], Journal of HeBei University of Technology,2002,8(31):19-24.
23. Chu C H, Gu J, Hou X, et al. A heuristic ant algorithm for solving QoS multicast problem[A], Proceedings of the 2002 Congress on Evolutionary Computation[C], Piscataway:IEEE,2002,1630-1635.
24.张舜,许毅.基于蚁群算法的多QoS约束的多播路由优化算法[J],武汉理工大学学报,2007,31(5)：939-942.
25.邵志伟,浦小祥.基于蚁群算法的自适应QoS路由优化[J],信息技术,2007,31(12)：41-43.
26. Hu J M, Yang Z S, Jian F. Study on the optimization methods of transit network based on ant algorithm[A], Proc of the IEEE Int Vehicle Electronics Conf[C], Tottori:IEEE,2001, 215-220.
27. Nouyan S. Agent-based approach to dynamic task allocation[A], Proc of 3rd Int Workshop on Ant Algorithm[C], Heidelberg:Springer-Verlag,2002,221-226.
28. Li Y J, Wu T J. A nested hybrid ant colony algorithm for hybrid production scheduling problems[J], Acta Automatica Sinica,2003,29(1):95-101.
29. Hou Y H, Wu Y W, Lu L J, et al. Economic dispatch of power systems based on generalized ant colony optimization method[J], Proceedings of the CSEE,2003,23(3): 59-64.
30.黄训诚,庄奕琪,耿阿囡.基于改进蚁群算法的配电网优化规划[J],西安交通大学学报,2007,41(6)：727-731.
31. El-Keib A A. Unit commitment using the ant colony search algorithm[A], Proc of the 2002 Int Conf on Power System Technology[C], Kunming:Proceedings of the CSEE, 2002,2-6.
32. Teng J H, Liu Y H. A novel ACS-based optimum switch relocation method[J], IEEE Trans on Power Systems,2003,18(1):113-120.
33. Hung S J. Enhancement of hydroelectric generation scheduling using ant colony system based optimization approaches[J], IEEE Trans on Energy Conversion,2001,16(3): 296-301.
34.段海滨,马冠军,王道波,等.一种求解连续空间优化问题的改进蚁群算法[J],系统仿真学报,2007,19(5)：974-977.
35. Jayaraman V K, Kulkarni B D, Karale S, et al. Ant colony framework for optimal design and scheduling of batch plants[J], Computers and Chemical Engineering,2000,24(8): 1901-1912.
36.杨冕,秦前清.基于无线传感器网络的路由协议[J],计算机工程与应用,2004,40(30)：130-131.
37.刘欣,杨家玮.基于OPNET的改进式泛洪路由仿真[J],数字通信世界,2007(5)：78-81.
38.范武,李力.无线传感器网络SPIN路由协议改进的方案[J],计算机与现代化,2007(3)：93-96.
39.赵奇,王汝传,孙力娟.无线传感器网络定向扩散协议研究及改进[J],计算机工程与设计,2007,28(12)：2825-2828.
40. Wendi B, Heinzelman, Anantha P, et al. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J], IEEE Transactions on wireless communications.2002, 1(4):660-670.
2. Angelo Brayner, Aretusa Lopes, Diorgens Meira, et al. Toward adaptive query processing in wireless sensor networks [J], Signal Processing,2007,87(12):2911-2933.
3.孙利民,李建中,陈渝,等.无线传感器网络[M],北京：清华大学出版社,2005,24-25.
4.郑相全.无线自组网技术[M],北京：清华大学出版社,2004,15-17.
5. Akyildiz I.F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J], IEEE Communication Magazine,2002,40(8):102-114.
6. Azzedine Boukerche, Xin Fei. A coverage-preserving scheme for wireless sensor network with irregular sensing range[J], Ad Hoc Networks,2007,5(8):1303-1316.
7.代航阳,徐红兵.无线传感器网络安全综述[J],计算机应用研究,2007,23(7)：12-17.
8. Roberto Di Pietro,Luigi V. Mancini, Sushil Jajodia. Providing secrecy in key management protocols for large wireless sensors networks [J], Ad Hoc Networks,2003,1(4):455-468.
9. Yaoyi Mao, Frank R, Kschischang, et al. Factor graph approach to link loss monitoring in wireless sensor networks[J], IEEE Journal on Selected Areas in Communications,2005, 23(12):820-829.
10. Olivier Powell, Pierre Leone, Jose Rolim. Energy optimal data propagation in wireless sensor networks[J], Journal of Parallel and Distributed Computing,2007,67(3):302-317.
11. Woo A, Culler D E. A transmission control scheme for media access in sensor networks[A], Proceedings of the ACM MobiCom'01[C], Italy:ACM Press,2001, 221-235.
12. Haythem Bany Salameh, Tao Shu, Marwan Krunz. Adaptive cross-layer MAC design for improved energy-efficiency in multi-channel wireless sensor networks[J], Ad Hoc Networks,2007,5(6):844-854.
13. Ye Wei, Heidemann J, Estrin D. An energy-efficient MAC protocol for wireless sensor network[A], Proceedings of the INFORCOM'2002[C], San Francisco:IEEE Computer Society,2002,1567-1576.
14. Noury N, Herve T, Rialle V, et al. Monitoring behavior in home using a smart fall sensor[A], Proceedings of the IEEE-EMBS Special Topic Conference on Micro technologies in Medicine and Biology[C], Lyon:IEEE Computer Society,2000,607-610.
15.柯文德,李家兰.蚁群算法及其在TSP中的应用[J],茂名学院学报,2007,17(1)：53-55.
16. M.Duran Toksari. Ant colony optimization approach to estimate energy demand of Turkey[J], Energy Policy,2007,35(8):3984-3990.
17. Wei Yi, Arun Kumar. Ant colony optimization for disaster relief operations [J], Transportation Research Part E:Logistics and Transportation Review,2007,43(6): 660-672.
18.刘立东,蔡淮,赵旭.一类自适应蚁群算法的收敛性分析[J],计算机应用,2007,27(B06)：73-75.
19.方旺盛,肖琴.蚁群算法的收敛性分析及其在TSP上的求解[J],计算机与数字工程,2007,35(9)：46-48.
20. Botee H M, Bonabeau E. Evolving ant colony optimization[J], Advances in Complex Systems,1998,1(2):149-159.
21. Dorigo M, Caro G, Gambardella L M. Ant algorithms for discrete optimization[J], Artificial Life,1999,5(3),137-172.
22. Junhua Gu, Xiang Dan, Song Jie, et al. Solving QoS multicast routing problem based on heuristic ant algorithm[J], Journal of HeBei University of Technology,2002,8(31):19-24.
23. Chu C H, Gu J, Hou X, et al. A heuristic ant algorithm for solving QoS multicast problem[A], Proceedings of the 2002 Congress on Evolutionary Computation[C], Piscataway:IEEE,2002,1630-1635.
24.张舜,许毅.基于蚁群算法的多QoS约束的多播路由优化算法[J],武汉理工大学学报,2007,31(5)：939-942.
25.邵志伟,浦小祥.基于蚁群算法的自适应QoS路由优化[J],信息技术,2007,31(12)：41-43.
26. Hu J M, Yang Z S, Jian F. Study on the optimization methods of transit network based on ant algorithm[A], Proc of the IEEE Int Vehicle Electronics Conf[C], Tottori:IEEE,2001, 215-220.
27. Nouyan S. Agent-based approach to dynamic task allocation[A], Proc of 3rd Int Workshop on Ant Algorithm[C], Heidelberg:Springer-Verlag,2002,221-226.
28. Li Y J, Wu T J. A nested hybrid ant colony algorithm for hybrid production scheduling problems[J], Acta Automatica Sinica,2003,29(1):95-101.
29. Hou Y H, Wu Y W, Lu L J, et al. Economic dispatch of power systems based on generalized ant colony optimization method[J], Proceedings of the CSEE,2003,23(3): 59-64.
30.黄训诚,庄奕琪,耿阿囡.基于改进蚁群算法的配电网优化规划[J],西安交通大学学报,2007,41(6)：727-731.
31. El-Keib A A. Unit commitment using the ant colony search algorithm[A], Proc of the 2002 Int Conf on Power System Technology[C], Kunming:Proceedings of the CSEE, 2002,2-6.
32. Teng J H, Liu Y H. A novel ACS-based optimum switch relocation method[J], IEEE Trans on Power Systems,2003,18(1):113-120.
33. Hung S J. Enhancement of hydroelectric generation scheduling using ant colony system based optimization approaches[J], IEEE Trans on Energy Conversion,2001,16(3): 296-301.
34.段海滨,马冠军,王道波,等.一种求解连续空间优化问题的改进蚁群算法[J],系统仿真学报,2007,19(5)：974-977.
35. Jayaraman V K, Kulkarni B D, Karale S, et al. Ant colony framework for optimal design and scheduling of batch plants[J], Computers and Chemical Engineering,2000,24(8): 1901-1912.
36.杨冕,秦前清.基于无线传感器网络的路由协议[J],计算机工程与应用,2004,40(30)：130-131.
37.刘欣,杨家玮.基于OPNET的改进式泛洪路由仿真[J],数字通信世界,2007(5)：78-81.
38.范武,李力.无线传感器网络SPIN路由协议改进的方案[J],计算机与现代化,2007(3)：93-96.
39.赵奇,王汝传,孙力娟.无线传感器网络定向扩散协议研究及改进[J],计算机工程与设计,2007,28(12)：2825-2828.
40. Wendi B, Heinzelman, Anantha P, et al. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J], IEEE Transactions on wireless communications.2002, 1(4):660-670.