基于ACS的无线传感器网络区分服务路由算法

doi:10.3969/j.issn.1000-436x.2013.10.013

摘要/Abstract

摘要：

针对无线传感器网络中数据传输的不同要求，将QoS分为3类，根据无线链路的特点提供区分服务。利用博弈论分析了数据传输在延迟、可靠性与网络能量开销之间的关系，基于改进的蚁群优化算法ACS(ant colony system)，设计了区分服务路由算法ADSGR(ant colony system based differentiated service and game-theory routing)，依据不同QoS要求，选择适当的路由，提高网络的整体性能和资源利用率。实验结果表明，与现有算法相比，该算法在数据传输的延迟、可靠性和能量开销上具有更好的性能。

关键词: 无线传感器网络, 蚁群优化, 区分服务, 博弈论, QoS路由

Abstract:

Aiming at the different requirements of data transmission in wireless sensor networks,QoS was divided into three services.By using game theory,the relationship among the delay,reliability and energy consumption during the process of data transmission was analyzed.Based on ACS (ant colony system),ACS based differentiated service and game-theory routing (ADSGR)was proposed.In accordance with the diverse QoS requirements,the ADSGR chooses the suitable paths,and improves network performance and resource utility.Experimental results show the ADSGR has better performance than some other routing algorithms in terms of the delay,reliability and energy consumption.

Key words: wireless sensor network, ant colony system, differentiated service, game theory, QoS routing

赵宏,胡智,闻英友. 基于ACS的无线传感器网络区分服务路由算法[J]. 通信学报, 2013, 34(10): 106-115.

Hong ZHAO,Zhi HU,Ying-you WEN. ACS based differentiated service routing algorithm in wireless sensor network[J]. Journal on Communications, 2013, 34(10): 106-115.

图/表 9

图1

图2

表1

图3

图4

图5

图6

图7

图8

参考文献 29

[1]	AKYILDIZ I F , SU W , SANKARASUBRAMANIAM Y . Wireless sensor networks:a survey[J]. Computer Networks, 2002,38(4): 393-422.
[2]	YICK J , MUKHERJEE B , GHOSAL D . Wireless sensor networks survey[J]. Computer Networks, 2008,52(2): 2292-2330.
[3]	文浩, 林闯, 任丰原 ,等. 无线传感器网络的QoS体系结构[J]. 计算机学报, 2009,32(3): 432-440. WEN H , LIN C , REN F Y ,et al. QoS architecture in wire ess sensor network[J]. Chinese Journal of Computer, 2009,32(3): 432-440.
[4]	DORIGO M , CARO G D . Ant algorithms for discrete optimization[J]. Artificial Life, 1999,5(3): 137-172.
[5]	DORIGO M , GAMBARDELLA L M . Ant colony system:a coopera-tive learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary Computation, 1997,1(1): 53-66.
[6]	DORIGO M , MANIEZZO V , COLOM I A . Ant system:optimizat n by a colony of cooperating agents[J]. IEEE Trans on Systems,Man,and Cybernetics:Part B, 1996,26(1): 29-41.
[7]	孙岩, 马华东, 刘亮 . 一种基于蚁群优化的多媒体传感器网络服务感知路由算法[J]. 电子学报, 2007,35(4): 705-711. SUN Y , MA HD , LIU L . An ant-colony optimization based service aware routing algorithm for multimedia sensor networks[J]. Chinese Journal of Electronics, 2007,35(4): 705-711.
[8]	崔艳荣, 李克清 . 传感器网络中基于蚁群优化的数据查询协议[J]. 软件学报, 2010,21(4): 793-801. CUI Y R , LI K Q . Data query protocol based on ant colony optimiza-tion for wireless sensor networks[J]. Chinese Journal f Software, 2010,21(4): 793-801.
[9]	曹啸, 王汝传, 黄海平 ,等. 无线多媒体传感器网络视频流多路径路由算法[J]. 软件学报, 2012,23(1): 108-121. CAO X , WANG R C , HUANG H P ,et al. Multi-path routing algorithm for video stream in wireless multimedia sensor networks[J]. Chinese Journal of Software, 2012,23(1): 108-121.
[10]	COBO L , QUINTERO A , PIERRE S . Ant-based routing for wireless multimedia sensor networks using multiple QoS metrics[J]. Computer Networks, 2010,54(17): 2991-3010.
[11]	OKDEM S , KARABOGA D . Routing in wireless sensor networks using ant colony optimization[A]. Proceedings of the First NASA/ESA Conference on Adaptive Hardware and Systems[C]. IEEE Press, 2006. 401-404.
[12]	FUDENBERG D , TIROLE J . Game Theory[M]. MIT Press, 1991.
[13]	MACHADO R , TEKINAY S . A survey of game-theoretic approaches in wireless sensor networks[J]. Computer Networks, 2008,52(8): 3047-3061.
[14]	SENGUPTA S , CHATTERJEE M , KWIAT K.A . A game theoretic framework for power control in wireless sensor networks[J]. IEEE Trans on computers, 2010,59(2): 231-242.
[15]	KANNAN R , SITHARAMA I S . Game-theoretic models for reliable path-length and energy-constrained routing with data aggregation in wireless sensor networks[J]. IEEE Journal on Selected Areas in Communication, 2004,22(6): 1141-1150.
[16]	KANNAN R,SARANGI S , IYENGAR S S , RAY L . Sensor-centric quality of routing in sensor networks[A]. Proceedings f IEEE Infocom[C]. San Francisco,CA, 2003. 692-701.
[17]	李慧芳, 姜胜明, 韦岗 . 无线传感器网络中基于博弈论的路由建模[J]. 传感器技术学报, 2007,20(9): 2075-2079. LI H F , JIAN S M . Game-theoretic modeling on routing in wireless sensor networks[J]. Chinese Journal of Sensors and Act 2007,20(9): 2075-2079.
[18]	曾加, 慕春棣 . 基于不完全信息博弈的传感器网络能量平衡路由[J]. 自动化学报, 2008,34(3): 317-322. ZENG J , MU C D . Game theory-based energy balance routing with incomplete information in wireless sensor networks[J]. ACTA Auto-matica Sinica, 2008,34(3): 317-322.
[19]	Koltsidas G , Pavlidou F N . A game theoretical approach to clustering of ad-hoc and sensor networks[J]. Telecommunication Systems, 2011,47: 81-93.
[20]	孙佩刚, 赵海, 罗玎玎 ,等. 无线传感器网络链路通信质量测量研究[J]. 通信学报, 2007,28(10): 14-22. SUN P G , ZHAO H , LUO D D ,et al. Study on measurement of link communication quality in wireless sensor networks[J]. Journal on Communication, 2007,28(10): 14-22.
[21]	SRINIVASAN K , KAZANDJIEVA M A , AGARWAL S ,et al. The ?-factor:measuring wireless link burstiness[A]. Proceed gs of the 6th ACM Conference on Embedded network sensor system(SenSys)[C]. Raleigh,NC,USA, 2008,29-42.
[22]	ZUNIGA M , KRISHNAMACHARI B . Analyzing the transitional region in low power wireless links[A]. Proceedings of IEEE SE-CON[C]. 2004. 517-526.
[23]	DE COUTO D S J , AGUAYO D , BICKET J C ,et al. A high-throughput path metric for multi-hop wireless routing[J]. Wire-less Networks, 2005,11(4): 419-434.
[24]	OMPRAKASH G , RODRIGO F , KYLE J ,et al. Collection tree proto-col[A]. Proceedings of the 7th ACM conference on Embedded net-work sensor system(SenSys)[C]. Berkeley,CA,USA, 2009. 1-14.
[25]	王兴伟, 秦佩玉, 郭磊 ,等. 基于混合人工鱼群的ABC支持型切换决策机制[J]. 通信学报, 2010,31(12): 72-81. WANG X W , QIN P Y , GUO L ,et al. Hybrid artificial fish swarm based handover decision scheme with ABC supported[J]. urnal on Communication, 2010,31(12): 72-81.
[26]	杨纶标, 高英仪 . 模糊数学原理与应用 (第四版)[M]. 广州: 华南理工大学出版社, 2006.41-49. YANG L B , GAO Y Y . Fuzzy Mathematics and Application ( urth edition)[M]. Guangzhou: South China University of Tech logy Press, 2006,41-49.
[27]	BUETTNER M , YEE G , ANDERSON E ,et al. X-MAC:a short preamble MAC protocol for duty-cycled wireless sensor networks[A]. Proceedings of the 4th ACM conference on Embedded network sensor system(SenSys)[C]. New York,USA, 2006,307-320.
[28]	LEVIS P , LEE N , WELSH M ,et al. TOSSIM:accurate and scalable simulation of entire tinyOS application[A]. Proceedings of the 1st ACM conference on Embedded network sensor system(SenSys)[C]. Los Angeles,CA,USA, 2003,126-137.
[29]	FELEMBAN E , LEE C G , EKICI E . MMSPEED:multipath mul-ti-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[J]. IEEE Trans on Mobile Comp ing, 2006,5(6): 738-754.

QoS分类	a	?	a_D	a_L	a_E	?
QoS-1	2	3	0.5	0	0.5	0.5
QoS-2	2	3	0	0.5	0.5	0.5
QoS-3	2	3	0.3	0.3	0.4	0.4