Title | ||
---|---|---|
When In-Network Processing Meets Time: Complexity and Effects of Joint Optimization in Wireless Sensor Networks |
Abstract | ||
---|---|---|
As sensornets are increasingly being deployed in mission-critical applications, it becomes imperative that we consider application QoS requirements in in-network processing (INP). Towards understanding the complexity of joint QoS and INP optimization, we study the problem of jointly optimizing packet packing (i.e., aggregating shorter packets into longer ones) and the timeliness of data delivery. We identify the conditions under which the problem is strong NP-hard, and we find that the problem complexity heavily depends on aggregation constraints (in particular, maximum packet size and re-aggregation tolerance) instead of network and traffic properties. For cases when the problem is NP-hard, we show that there is no polynomial-time approximation scheme (PTAS); for cases when the problem can be solved in polynomial time, we design polynomial time, offline algorithms for finding the optimal packet packing schemes. To understand the impact of joint QoS and INP optimization on sensornet performance, we design a distributed, online protocol emph{tPack} that schedules packet transmissions to maximize the local utility of packet packing at each node. Using a testbed of 130 TelosB motes, we experimentally evaluate the properties of tPack. We find that jointly optimizing data delivery timeliness and packet packing significantly improve network performance. Our findings shed light on the challenges, benefits, and solutions of joint QoS and INP optimization, and they also suggest open problems for future research. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1109/RTSS.2009.13 | RTSS |
Keywords | Field | DocType |
schedules packet transmission,np-hard,data delivery,sensor network,mission-critical applications,quality of service,shorter packet,packet packing,polynomial time,optimal packet packing scheme,-wireless network,polynomial approximation,packet radio networks,polynomial-time approximation scheme,joint optimization,open problem,qos,in-network processing meets time,in-network processing,maximum packet size,real-time,wireless sensor networks,optimizing packet packing,joint qos,wireless network,inp optimization,re-aggregation tolerance,wireless sensor network,np hard,optimization,polynomials,routing,network performance,polynomial time approximation scheme,real time,time complexity | Wireless network,Computer science,Network packet,Computer network,Quality of service,Real-time computing,Schedule,Time complexity,Wireless sensor network,Polynomial-time approximation scheme,Network performance,Distributed computing | Conference |
ISSN | ISBN | Citations |
1052-8725 | 978-0-7695-3875-4 | 6 |
PageRank | References | Authors |
0.47 | 31 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Qiao Xiang | 1 | 74 | 9.11 |
Jin-hong Xu | 2 | 11 | 2.70 |
Xiaohui Liu | 3 | 44 | 3.34 |
Hongwei Zhang | 4 | 935 | 67.71 |
Loren J. Rittle | 5 | 110 | 6.15 |