无线传感器网络能量最优的QoS路由发现方法
|
摘要
无线传感器网络(WSN)是由大量低成本且具有传感、数据处理和无线通信能力的传感器节点自组织构成的多跳网络。由于无线传感器网络不受有线网络约束，组网快捷，具有广阔的应用空间，因而吸引了大量研究者的注意。
无线传感器网络中的节点一般采用电池供电，可以使用的电量非常有限，而且电池的更换是非常困难，但是其的生存时间却要求长达数月甚至数年，因此，大部分研究都致力于如何建立有效的方案来增长网络的生存期。
本文针对无线传感器网络的动态网络环境和节点能源受限且通常无法补充的能源特性等不利因素，提出了一种可以实现能量最优的QoS路由发现方法。该方法利用节点选择机制和节点邻居表来建立满足QoS带宽需求的可供选择的节点集合，从而减少路由发现过程中的所要监测的节点数量。所提方法还构建了无线传感器网络的能量评价模型和节点能耗权重模型，使用遗传算法从可供选择的节点集合中构建可实现能量最优的QoS路由，自适应的实现对节点调度，从而延长无线传感器网络的寿命。通过实验仿真与分析，给出了本文遗传算法的控制参数的选择区间。实验结果显示本文提出的可实现能量最优的QoS路由发现方法对无线传感器网络具有更好的适应性且能保证其有更长的寿命。
The wireless sensor networks (WSN), composed by sensors, microprocessor and wireless communication interface, is a multiple-hop and self-organized networks. The research of WSN has attracted lots of attentions because of its wide applications in resent years.
Since WSN is characterized by its limited battery-supplied power, extensive research efforts have been devoted to the design of efficient power saving policy to increase its lifetime.
In order to overcome the negative factors due to the natural characteristics of WSN, we present a new quality of QoS route discovery method which could guarantee the requirement of QoS and has better network lifetime. The method utilizes the node selection system and node's neighbor table to construct the set of candidate node in which the node's left bandwidth meet the requirement of the mission. So the number of the node which is supposed to be detected will reduce. In order to maximize the WSN's lifetime, the genetic algorithm (GA) utilizes the energy estimate model and node energy consumption weight model which are constructed to adaptive deal with the nodes's scheduling problem in WSN. The simulations and the analysis show the choosing interval of the controlling parameters proposed by the GA. The experiment results show the QoS route discovery method with the implementation of best energy for WSN has better adaptability and longer lifetime.
无线传感器网络中的节点一般采用电池供电，可以使用的电量非常有限，而且电池的更换是非常困难，但是其的生存时间却要求长达数月甚至数年，因此，大部分研究都致力于如何建立有效的方案来增长网络的生存期。
本文针对无线传感器网络的动态网络环境和节点能源受限且通常无法补充的能源特性等不利因素，提出了一种可以实现能量最优的QoS路由发现方法。该方法利用节点选择机制和节点邻居表来建立满足QoS带宽需求的可供选择的节点集合，从而减少路由发现过程中的所要监测的节点数量。所提方法还构建了无线传感器网络的能量评价模型和节点能耗权重模型，使用遗传算法从可供选择的节点集合中构建可实现能量最优的QoS路由，自适应的实现对节点调度，从而延长无线传感器网络的寿命。通过实验仿真与分析，给出了本文遗传算法的控制参数的选择区间。实验结果显示本文提出的可实现能量最优的QoS路由发现方法对无线传感器网络具有更好的适应性且能保证其有更长的寿命。
The wireless sensor networks (WSN), composed by sensors, microprocessor and wireless communication interface, is a multiple-hop and self-organized networks. The research of WSN has attracted lots of attentions because of its wide applications in resent years.
Since WSN is characterized by its limited battery-supplied power, extensive research efforts have been devoted to the design of efficient power saving policy to increase its lifetime.
In order to overcome the negative factors due to the natural characteristics of WSN, we present a new quality of QoS route discovery method which could guarantee the requirement of QoS and has better network lifetime. The method utilizes the node selection system and node's neighbor table to construct the set of candidate node in which the node's left bandwidth meet the requirement of the mission. So the number of the node which is supposed to be detected will reduce. In order to maximize the WSN's lifetime, the genetic algorithm (GA) utilizes the energy estimate model and node energy consumption weight model which are constructed to adaptive deal with the nodes's scheduling problem in WSN. The simulations and the analysis show the choosing interval of the controlling parameters proposed by the GA. The experiment results show the QoS route discovery method with the implementation of best energy for WSN has better adaptability and longer lifetime.
引文
[1]RenFeng yuan, HuangHai ning, ChuangLin. Wirelesssensornetworks [J]. Journal of Software,2003,14(7): 1282-1291.
[2]Feng Zhao. Wireless sensor networks: a new computing platform for tomorrow's Internet.Emerging Technologies: Frontiers of Mobile and Wireless Communication, 2004.Proceedings of the IEEE 6th Circuits and Systems Symposium on Volume 1, Vol. 1:1-27.
[3]Johnson P,et al. Remote continuou physiological monitoring in the home. Journal of Telemedicine and Telecare.1996, 2(2):107-113.
[4]Ogawa M, et al. Fully automated biosignal acquisition in daily routine through 1 month. In: Intl. Conf. on IEEE-EMBS. Hong Kong, 1998: 1947-1950.
[5]Celler B G,et al.An instrumentation system for the remote Monitoring changes in functional health status of the elderly.In: Intl. Conf. IEEE - EMBS.New York.1994: 908-909.
[6]Coyle G. et al.Home telecare for the elderly. Journal of Telemedicine and Telecare, 1995(1): 183-184.
[7]J.R.Polastre. Design and implementation of wireless sensor networks for habitat monitoring. Master's thesis, University of California at Berkeley, 2003
[8]Nagpal,R.,Shrobe,H.and Bachrach, J.Organizing a globalcoordinate system from local information on an ad hoc sensornetwork. In Information Processing in Sensor Networks: Secondlnternational Workshop, IPSN 2003 (Palo Alto, April 2003), no. 2634 in Lecture Notes in Computer Science, Springer-Verlag: 333-348.
[9]Man Wah Chiang,Zilic Z, Radecka K,Chenard J.-S.Architectures of increased availability wireless sensor network nodes. Test Conference, 2004. Proceedings. International 2004:1232-1241.
[10]Akyildiz I.F,Weilian Su,Sankarasubramaniam Y,Cayirci E.A survey on sensor networks. Communications Magazine. Aug. 2002,IEEE, Volume: 40 , Issue 8:102 -114.
[11]Greenstein B,Estrin D,Govindan R ,Ratnasamy S,Shenker S. DIFS. a distributed index for features in sensor networks.Sensor Network Protocols and Applications, 2003. Proceedings of the First IEEE. 2003 IEEE International Workshop on 11 May 2003: 163 -173.
[12] 杨少军，史浩山，陈敏．无线传感器网络QoS路由的研究与仿真[J]．传感技术学报，2005，18(3)：454-459．
[13] Kemal A, Mohamed Y.Energy and QoS Aware Routing in Wireless Sensor Networks.Cluster Computing [J], 2005,Vol8:179-188.
[14] Ying Z, Markus P.J.F, Lukas D.K.Smart Routing with Learning-Based QoS-Aware Meta-strategies[C],In:QofIS 2004,LNCS 3266:298-307.
[15] 姜爱全，叶晓国，吴家皋．无线／移动网络基于遗传算法的带宽适应方案[J]．计算机研究与发展，2004，41(9)：1453-1459．
[16] Pi-Rong Sheu,Chia-Hung Chien,Chin-Pin Hu et al.An Efficient Genetic Algorithm for the Power-Based QoS Many-to-one Routing Problem for Wireless Sensor Networks [C].ICOIN 2005,LNCS 3391:275-282.
[17] E.Crawley, R.Nair, B.Rajagopalan et al. A Framework for Qos-based Routing in the Internet.RFC2386, 1998.
[18] Vern Paxson, Towards a Framework for Defining Internet Performance Metrics.in: INET, 1996
[19] Z.Wang, J. Crowcroft. Quality of service routing for supporting multimedia applications.IEEE JSAC,1996,14:1228-1234.
[20] (美)Larry L．Peterson,Bruce S．Davie著．计算机网络．第二版．叶新铭等译．北京．机械工业出版社，2001．162-198．
[21] 黄晓雯，贺细平，唐贤英．基于遗传算法的Qos路由选择与仿真．计算机仿真[J]，2003，20(6)：43-46．
[22] 何小燕，费翔，罗军周，吴介一．Internet中一种基于遗传算法的Qos路由选择策略[J]．计算机学报，2000，23(11)：1172～1178．
[23] Z.Wang, J. Crowcroft. Quality of service routing for supporting multimedia applications.IEEE JSAC,1996,14:1228-1234.
[24] 刘勇，康立山，陈毓屏．非数值并行算法(第二册)—遗传算法．北京．科学出版社，2000：22-25．
[25] 周明，孙树栋，遗传算法原理及应用，北京．国防工业出版社，2002：11-64．．
[26] 陈国良，王煦法，庄镇泉等．遗传算法及其应用．北京．人民邮电出版社．1996：96-97．
[27] Qingfu Zhang, Yiu-Wing leung.An Orthogonal Genetic Algorithm for Multimedia Multicast Routing. IEEE Transactions on evolutionary communication 1999, 3(1):53-62
[28] 刘吴旸．遗传算法研究及遗传算法工具箱开发．天津大学工程硕士学位论文．2005：8-10．
[29] BERANRD M.WAXMAN.Routing of Multipoint Connections.IEEE JSAC, 1988, 6(9): 1617-1622.
[30] G.N.Rouskas. Multicast routing with end-to-end delay-and delay-variation constraints. IEEE JSAC,1997,15(3):346-356.
[31] Genui Zhou, Mitsuo Gen, Tianzu Wu. A New Approach to The Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm. IEEE International Conference on Systems,Man and Cybernetics, 1996, 4: 2683-2688.
[32] 刘莹，吴建平．求解带时延约束组播路由问题的启发式遗传算法[J]．计算机研究与发展，2003，40(3)：381-386．
[33] Genui Zhou,Mitsuo Gen,Tianzu Wu.A New Approach to The Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm. IEEE International Conference on Systems, Man and Cybernetics, 1996, 4: 2683-2688.
[34] Michalewicz.Z, Dasgupta.D, Le Riche.R.G. et al. Evolutionary Algorithms for Constrained Engineering Problems.Computers and Industrial Engineering, 1996,30(4):851-870.
[35] 朱战立．数据结构．西安，西安电子科技大学出版社，2003：187-190．
[36] Kemal A, Mohamed Y.Energy and QoS Aware Routing in Wireless Sensor Networks.Cluster Computing [J], 2005,Vol8:179-188.
[37] 李云，赵为粮，隆可平等．无线Ad Hoc网络支持QoS的研究进展与展望．软件学报[J]，2004，15(10)：1885—1889．
[38] Chenxi Z,Corson MS.QoS routing for mobile ad hoc networks[A]. INFOCOM2002, Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies,New York,U.S.A.2002.
[39] 李明遗传算法的改进及其在优化问题中的应用．吉林大学硕士学位论文．2004：7-14．
[40] 郑彦兴，田箐，窦文华．基于遗传算法的有矢量约束的多播路由计算[J]．计算机学报，2003，26(6)：746-752．
[41] 李美莲．遗传算法在QoS组播路由优化中的应用研究．中北大学硕士学位论文．2005：47-51．
[42] 张文修，梁怡．遗传算法的数学基础[M]．西安交通大学出版社．2003．
[43] 赵舒展．遗传算法研究与应用．浙江工业大学硕士学位论文．2001：55-63．
[44] 陈燕．基于遗传算法的选播QoS路由算法研究与仿真实现．广西大学硕士学位论文．2003：17-50．
[45] Ye W, Heidemann J,Estrin D.Medium access control with coordinated adaptive sleeping for wireless sensor networks [J]. IEEE/ACM Transactions on Networking, June 2004,12 (3):493-506.
[46] IEEE 802. 15 [J/OL], Working Group for Wireless Personal Area Networks, http://www.ieee802.org/15/.
[47] W.Heinzelman.Application-specific Protocol Architectures for Wireless Networks [D].PH.D. thesis, MIT, 2000.
[48] 陈敏．OPNET网络仿真．清华大学出版社．2004．
[49] 张剑．基于OPNET建模仿真方法研究．武汉理工大学硕士学位论文．2005：7-54．
[50] C. Intanagonwiwat, R. Govindan, D. Estrin. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks [C]. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networks (MobiCO, August 2000).
[2]Feng Zhao. Wireless sensor networks: a new computing platform for tomorrow's Internet.Emerging Technologies: Frontiers of Mobile and Wireless Communication, 2004.Proceedings of the IEEE 6th Circuits and Systems Symposium on Volume 1, Vol. 1:1-27.
[3]Johnson P,et al. Remote continuou physiological monitoring in the home. Journal of Telemedicine and Telecare.1996, 2(2):107-113.
[4]Ogawa M, et al. Fully automated biosignal acquisition in daily routine through 1 month. In: Intl. Conf. on IEEE-EMBS. Hong Kong, 1998: 1947-1950.
[5]Celler B G,et al.An instrumentation system for the remote Monitoring changes in functional health status of the elderly.In: Intl. Conf. IEEE - EMBS.New York.1994: 908-909.
[6]Coyle G. et al.Home telecare for the elderly. Journal of Telemedicine and Telecare, 1995(1): 183-184.
[7]J.R.Polastre. Design and implementation of wireless sensor networks for habitat monitoring. Master's thesis, University of California at Berkeley, 2003
[8]Nagpal,R.,Shrobe,H.and Bachrach, J.Organizing a globalcoordinate system from local information on an ad hoc sensornetwork. In Information Processing in Sensor Networks: Secondlnternational Workshop, IPSN 2003 (Palo Alto, April 2003), no. 2634 in Lecture Notes in Computer Science, Springer-Verlag: 333-348.
[9]Man Wah Chiang,Zilic Z, Radecka K,Chenard J.-S.Architectures of increased availability wireless sensor network nodes. Test Conference, 2004. Proceedings. International 2004:1232-1241.
[10]Akyildiz I.F,Weilian Su,Sankarasubramaniam Y,Cayirci E.A survey on sensor networks. Communications Magazine. Aug. 2002,IEEE, Volume: 40 , Issue 8:102 -114.
[11]Greenstein B,Estrin D,Govindan R ,Ratnasamy S,Shenker S. DIFS. a distributed index for features in sensor networks.Sensor Network Protocols and Applications, 2003. Proceedings of the First IEEE. 2003 IEEE International Workshop on 11 May 2003: 163 -173.
[12] 杨少军，史浩山，陈敏．无线传感器网络QoS路由的研究与仿真[J]．传感技术学报，2005，18(3)：454-459．
[13] Kemal A, Mohamed Y.Energy and QoS Aware Routing in Wireless Sensor Networks.Cluster Computing [J], 2005,Vol8:179-188.
[14] Ying Z, Markus P.J.F, Lukas D.K.Smart Routing with Learning-Based QoS-Aware Meta-strategies[C],In:QofIS 2004,LNCS 3266:298-307.
[15] 姜爱全，叶晓国，吴家皋．无线／移动网络基于遗传算法的带宽适应方案[J]．计算机研究与发展，2004，41(9)：1453-1459．
[16] Pi-Rong Sheu,Chia-Hung Chien,Chin-Pin Hu et al.An Efficient Genetic Algorithm for the Power-Based QoS Many-to-one Routing Problem for Wireless Sensor Networks [C].ICOIN 2005,LNCS 3391:275-282.
[17] E.Crawley, R.Nair, B.Rajagopalan et al. A Framework for Qos-based Routing in the Internet.RFC2386, 1998.
[18] Vern Paxson, Towards a Framework for Defining Internet Performance Metrics.in: INET, 1996
[19] Z.Wang, J. Crowcroft. Quality of service routing for supporting multimedia applications.IEEE JSAC,1996,14:1228-1234.
[20] (美)Larry L．Peterson,Bruce S．Davie著．计算机网络．第二版．叶新铭等译．北京．机械工业出版社，2001．162-198．
[21] 黄晓雯，贺细平，唐贤英．基于遗传算法的Qos路由选择与仿真．计算机仿真[J]，2003，20(6)：43-46．
[22] 何小燕，费翔，罗军周，吴介一．Internet中一种基于遗传算法的Qos路由选择策略[J]．计算机学报，2000，23(11)：1172～1178．
[23] Z.Wang, J. Crowcroft. Quality of service routing for supporting multimedia applications.IEEE JSAC,1996,14:1228-1234.
[24] 刘勇，康立山，陈毓屏．非数值并行算法(第二册)—遗传算法．北京．科学出版社，2000：22-25．
[25] 周明，孙树栋，遗传算法原理及应用，北京．国防工业出版社，2002：11-64．．
[26] 陈国良，王煦法，庄镇泉等．遗传算法及其应用．北京．人民邮电出版社．1996：96-97．
[27] Qingfu Zhang, Yiu-Wing leung.An Orthogonal Genetic Algorithm for Multimedia Multicast Routing. IEEE Transactions on evolutionary communication 1999, 3(1):53-62
[28] 刘吴旸．遗传算法研究及遗传算法工具箱开发．天津大学工程硕士学位论文．2005：8-10．
[29] BERANRD M.WAXMAN.Routing of Multipoint Connections.IEEE JSAC, 1988, 6(9): 1617-1622.
[30] G.N.Rouskas. Multicast routing with end-to-end delay-and delay-variation constraints. IEEE JSAC,1997,15(3):346-356.
[31] Genui Zhou, Mitsuo Gen, Tianzu Wu. A New Approach to The Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm. IEEE International Conference on Systems,Man and Cybernetics, 1996, 4: 2683-2688.
[32] 刘莹，吴建平．求解带时延约束组播路由问题的启发式遗传算法[J]．计算机研究与发展，2003，40(3)：381-386．
[33] Genui Zhou,Mitsuo Gen,Tianzu Wu.A New Approach to The Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm. IEEE International Conference on Systems, Man and Cybernetics, 1996, 4: 2683-2688.
[34] Michalewicz.Z, Dasgupta.D, Le Riche.R.G. et al. Evolutionary Algorithms for Constrained Engineering Problems.Computers and Industrial Engineering, 1996,30(4):851-870.
[35] 朱战立．数据结构．西安，西安电子科技大学出版社，2003：187-190．
[36] Kemal A, Mohamed Y.Energy and QoS Aware Routing in Wireless Sensor Networks.Cluster Computing [J], 2005,Vol8:179-188.
[37] 李云，赵为粮，隆可平等．无线Ad Hoc网络支持QoS的研究进展与展望．软件学报[J]，2004，15(10)：1885—1889．
[38] Chenxi Z,Corson MS.QoS routing for mobile ad hoc networks[A]. INFOCOM2002, Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies,New York,U.S.A.2002.
[39] 李明遗传算法的改进及其在优化问题中的应用．吉林大学硕士学位论文．2004：7-14．
[40] 郑彦兴，田箐，窦文华．基于遗传算法的有矢量约束的多播路由计算[J]．计算机学报，2003，26(6)：746-752．
[41] 李美莲．遗传算法在QoS组播路由优化中的应用研究．中北大学硕士学位论文．2005：47-51．
[42] 张文修，梁怡．遗传算法的数学基础[M]．西安交通大学出版社．2003．
[43] 赵舒展．遗传算法研究与应用．浙江工业大学硕士学位论文．2001：55-63．
[44] 陈燕．基于遗传算法的选播QoS路由算法研究与仿真实现．广西大学硕士学位论文．2003：17-50．
[45] Ye W, Heidemann J,Estrin D.Medium access control with coordinated adaptive sleeping for wireless sensor networks [J]. IEEE/ACM Transactions on Networking, June 2004,12 (3):493-506.
[46] IEEE 802. 15 [J/OL], Working Group for Wireless Personal Area Networks, http://www.ieee802.org/15/.
[47] W.Heinzelman.Application-specific Protocol Architectures for Wireless Networks [D].PH.D. thesis, MIT, 2000.
[48] 陈敏．OPNET网络仿真．清华大学出版社．2004．
[49] 张剑．基于OPNET建模仿真方法研究．武汉理工大学硕士学位论文．2005：7-54．
[50] C. Intanagonwiwat, R. Govindan, D. Estrin. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks [C]. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networks (MobiCO, August 2000).