无线传感器网络中基于链路质量的路径延时分析

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

摘要/Abstract

摘要：

基于链路质量给出了路径满足实时性概率的上界，并证明了计算其上界的时间复杂度为指数级。另外在考虑链路质量的基础上，提出了一种在给定的延迟阈值下最大化端到端数据分组发送成功概率的贪心算法(RROP)。根据给定的延迟阈值和链路质量，RROP算法通过设置每跳链路的最大重传次数来优化端到端数据分组发送成功的概率。证明该算法能够在多项式时间内找到最优解并且通过该最优解获得路径满足实时性概率的一个近似最优的下界。实验结果表明给出的路径延迟分析上界和下界是准确的，并且提出的RROP算法在节省能量和满足实时性上比传统的方法能够获得高出10%以上的性能。

关键词: 无线传感器网络, 路径延迟, 实时, 链路质量

Abstract:

The upper bound of the probability of a path meeting the deadline was given based on link quality, of which the time complexity was proved to be exponential. Moreover, the greedy algorithm (RROP) was proposed to maximize the end-to-end packet deliver ratio under a given deadline, considering the quality of each link. The RROP algorithm optimizes the end-to-end packet deliver ratio by setting the maximum number of retransmissions of each link along the path based on the deadline and link quality. It was proved that the proposed method can find the optimal solution in a polynomial time, and with which could achieve an approximate optimal lower bound of the probability for a path meeting the deadline. Finally, the experimental results show that the upper and lower bounds are accurate, and the proposed algorithm can perform 10% better than the traditional method, in terms of energy consumption and delay.

Key words: WSN, path delay, real-time, link quality

陈权,高宏. 无线传感器网络中基于链路质量的路径延时分析[J]. 通信学报, 2014, 35(6): 100-109.

Quan CHEN,Hong GAO. Link quality based path delay analysis in wireless sensor networks[J]. Journal on Communications, 2014, 35(6): 100-109.

图/表 10

图1

图2

图3

图4

图5

图6

表1

表2

表3

表4

参考文献 25

[1]	AKYILDIZ I F , SU W , SANKARASUBRAMANIAM Y , et al. Wire-less sensor networks: a survey[J]. Computer Networks, 2002,38 (4): 393-422.
[2]	孙利民，李建中，陈渝 . 无线传感器网络[J]. 北京：清华大学出版社， 2005. SUN L M , LI J Z , CHEN Y . Wireless Sensor Networks[M]. Beijing: Tsinghua University Press, 2005.
[3]	STANKOVIC J A , ABDELZAHER T E , LU C , et al. Real-time communication and coordination in embedded sensor networks[J]. Proceedings of the IEEE, 2003,91(7): 1002-1022.
[4]	WANG J L , DONG W , CAO Z C , et al. On the delay performance analysis in a large-scale wireless sensor network[A]. Proceedings of IEEE RTSS, San Juan, Puerto Rico, 2012.
[5]	WANG J L , LIU Y H , HE Y , et al.QoF: towards comprehensive path quality measurement in wireless sensor networks[J]. IEEE Transac-tions on Parallel and Distributed Systems, 2014,25(4): 1003-1013.
[6]	COUTO D , AGUAYO D , BICKET J , et al. A high-throughput path metric for multi-hop wireless routing[A]. Proceedings of ACM Mobi-Com, San Diego, California, USA, 2003.134-146.
[7]	BURCHARD A , LIEBEHERR J , PATEK S . A min-plus calculus for end to end statistical service guarantees[J]. IEEE Transactions on In-formation Theory, 2006,52(9): 4105-4114.
[8]	QIU T , XIA F , FENG L , et al. Queueing theory-based path delay analysis of wireless sensor networks[J]. Advances in Electrical and Computer Engineering, 2011,11(2): 3-8.
[9]	LEHOCZKY J P . Real-time queueing network theory[A]. Proceedings of IEEE RTSS[C]. San Francisco, USA, 1997. 58-67.
[10]	WANG Y , VURAN M C , GODDARD S . Cross-layer analysis of the end-to-end delay distribution in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2012,20(1): 305-318.
[11]	SAIFULLAH A , XU Y , LU C Y , et al. End-to-end delay analysis for fixed priority scheduling in wirelessHART networks[A]. Proceedings of Real-Time and Embedded Technology and Applications Sympo-sium (RTAS)[C]. Chicago, USA, 2011. 150-159.
[12]	SAIFULLAH A , XU Y , LU C Y , et al. Real-time scheduling for wirelessHART networks[A]. Proceedings of IEEE RTSS[C]. San Diego, CA, 2010. 150-159.
[13]	SAKURAI T , VU H . Mac access delay of IEEE 802.11 DCF[J]. IEEE Transactions on Wireless Communications, 2007,6(5): 1702-1710.
[14]	TICKOO O , SIKDAR B . Modeling queueing and channel access delay in unsaturated IEEE 802.11 random access mac based wireless networks[J]. ACM/IEEE Transactions on Networking, 2008,16(4): 878-891.
[15]	HOU I , KUMAR P R . A survey of recent results on real-time wireless networking[A]. Proceedings of Real-time Wireless for Industrial Ap-plications[C]. CPS Week, Chicago, 2011.
[16]	WANG Y , VURAN M C , GODDARD S . Analysis of event detection delay in wireless sensor networks[A]. Proceedings of IEEE INFO-COM[C]. Shanghai, China, 2011.1296-1304.
[17]	GU Y , HE T , LIN M G , et al. Spatiotemporal delay control for low-duty-cycle sensor networks[A]. roceedings of IEEE RTSS[C]. Washington , USA, 2009.127-137.
[18]	PUCHA H , ZHANG Y , MAO Z M , et al. Understanding network delay changes caused by routing events[A]. Proceedings of ACM SIGMETRICS[C]. New York, NY, USA, 2007.73-84.
[19]	LEE M , DUFFIELD N G , KOMPELLA R R . Not all microseconds are equal: fine-grained per-flow measurements with reference latency interpolation[A]. Proceedings of ACM SIGCOMM[C]. New Delhi, India, 2010.
[20]	WILSON C , BALLANI C H , KARGIANNIS T , et al. Better never than late: Meeting deadlines in data center networks[A]. Proceedings of ACM SIGCOMM[C]. Toronto, Ontario, Canada, 2011.
[21]	CTP[EB/OL]. , 2007.
[2]	陈权，高宏 .RSPEED：无线传感器网络中基于不确定延迟的可靠实时路由[J]. 通信学报， 2013,34(8): 110-119. CHEN Q , GAO H .RSPEED: the reliability and real-time routing based onuncertain delay in wireless sensor network[J]. Journal on Communications, 2013,34(8): 110-119.
[23]	LIN S , ZHOU G , WHITEHOUSE K , et al. Towards stable network performance in wireless sensor networks[A]. Proceedings of Sen-Sys[C]. New York, NY, USA, 2006.
[24]	KROGMANN M , HEIDRICH M , BICHLER D , et al. Reliable real-time routing in wireless sensor and actuator networks[J]. ISRN Communications and Networking, 2011.(10): 1-8.
[25]	Network simulator[EB/OL]. , 2009.

		DMR
延迟阈值/s
延迟阈值/s	RROP	BASELINE	NORMAL
0.096 000	0.513 020	0.562 700	0.517 588
0.108 000	0.387 056	0.493 729	0.422 111
0.120 000	0.300 552	0.404 868	0.351 759
0.132 000	0.223 204	0.389 111	0.316 583
0.144 000	0.167 481	0.279 317	0.296 482
0.156 000	0.127 911	0.236 564	0.291 457

		DR
延迟阈值/s
延迟阈值/s	RROP	BASELINE	NORMAL
0.096 000	0.069 651	0.020 100	0.236 180
0.108 000	0.060 913	0.015 075	0.170 854
0.120 000	0.039 800	0.025 380	0.100 502
0.132 000	0.030 927	0.039 408	0.065 326
0.144 000	0.035 532	0.010 362	0.045 226
0.156 000	0.024 752	0.0	0.040 201

		DMR
跳数
跳数	RROP	BASELINE	NORMAL
5	0.196 028	0.292 575	0.289 340
6	0.160 125	0.204 331	0.292 308
7	0.144 190	0.203 449	0.205 128
8	0.223 204	0.389 111	0.316 583
9	0.208 746	0.391 092	0.295 000

		DR
跳数
跳数	RROP	BASELINE	NORMAL
5	0.059 405	0.029 268	0.101 522
6	0.055 837	0.034 482	0.082 051
7	0.040 816	0.020 100	0.071 794
8	0.030 927	0.040 609	0.065 326
9	0.035 532	0.008 849	0.055