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

Link quality based path delay analysis in wireless sensor networks

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

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.