Algorithms for bounding end-to-end delays in Wireless Sensor Networks

作     者：Lang, Xiaofeng Chin, Kwan-Wu 

作者机构：Univ Wollongong Sch Elect Comp & Telecommun Engn Wollongong NSW 2522 Australia 

出 版 物：《WIRELESS NETWORKS》 (无线网络)

年 卷 期：2014年第20卷第7期

页      面：2131-2146页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Wireless Sensor Networks Approximation algorithms Bounded delays Binary Integer Linear Program 

摘      要：Wireless Sensor Networks (WSNs) have many characteristics that are attractive to a myriad of applications. In particular, nodes employ multi-hop communications to collaboratively forward sensed data back to one or more sinks. In this context, reducing the end-to-end delay between the sink and sensor/source nodes is of interest to many applications. In particular, those that require a fixed, upper bound on end-to-end delays. To this end, we focus on bounding the end-to-end delay from the sink to each source. We first formulate the problem as a Binary Integer Program (BIP). As the problem is NP-hard, this paper proposes and studies two centralized, heuristic algorithms: Tabu and Domino. The key approach used by both algorithms is to determine the minimal number of extra wake-up slots required by a given network in order to ensure the delay of all end-to-end paths is within a given bound. We conducted two sets of experiments. The first set compares BIP, Tabu, and Domino in WSNs with up to 80 nodes. These experiments serve to compare the proposed algorithms against BIP, which become computationally expensive in large scale WSNs. The results show that, compared to BIP, the number of additional wake-up times generated by Tabu and Domino are within 5 and 10 % of the optimal solution. In the second set of experiments, which evaluates the algorithms in WSNs with 100-500 nodes, the average number of extra wake-up slots activated by Domino is 13 % greater than Tabu. These algorithms have a time complexity of and respectively, where is the number of nodes, is the number of slots in one period, and is the maximum number of iterations carried out by the Tabu algorithm.