ε-近似和加权公平性保证的无线传感器网络拥塞控制算法

ε-Approximation and Weighted Fairness Guaranteed Congestion Control Algorithm for Wireless Sensor Networks

针对现有的无线传感器网络拥塞控制算法中很少考虑数据压缩和加权公平性的问题,提出了一种ε近似和加权公平性保证的拥塞控制算法.首先,我们对传感器节点产生的时间序列采用贪心分段常值ε近似(GreedyPiecewise Constantε-Approximation,GPCA)的策略,极大地减少了数据通信量.其次,我们给出了具有加权公平性保证的拥塞控制算法(Weighted Fairness Guaranteed Congestion Control Algorithm,WFCC),并首次给出了公平性度量的下界1-(10c/9)2,其中c为常数且0<c<0.2.实验结果表明,GPCA具有很好的压缩性能,WFCC达到了较高的吞吐量和加权公平性(95%以上).

In a wireless sensor network,congestion problem not only causes packet loss,but also leads to delay increase and energy consumption.Most of the existing congestion control algorithms for wireless sensor networks seldom concern the combined problem of data compression and weighted fairness.In order to address this problem,a greedy piecewise constant ε-approximation algorithm,GPCA,and a novel decentralized congestion control algorithm WFCC are proposed in this paper.GPCA approximates a subsequence using a constant and guarantees that the error between the real sequence and the approximation sequence is less than or equal to ε.In addition,we prove the optimality of constant ε-approximation in theory.WFCC not only mitigates congestion,but also guarantees the weighted fairness among all sensor nodes.Importantly,we give a lower bound of weighted fairness metric 1-（10c/9）2 where c is a constant and 0c0.2.We evaluate GPCA using Intel Lab Data,and the results show that GPCA has great compression performance.In addition,we evaluate the algorithm WFCC in a 22-node wireless sensor network by TOSSIM.The results of simulation demonstrate that WFCC achieves high throughput and weighted fairness（above 95% on average）.