Paper Info
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). Toward 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 reaggregation 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 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 and considering real-world aggregation constraints 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
2011
10.1109/TMC.2011.81
IEEE Trans. Mob. Comput.
Keywords
Field
DocType
open problem,optimal packet packing scheme,maximum packet size,schedules packet transmission,packet packing,joint qos,polynomial time,joint optimization,in-network processing meets time,inp optimization,optimizing packet packing,wireless sensor networks,shorter packet,real time,optimization,quality of service,time complexity,wireless network,protocols,wireless sensor network,polynomials,computational complexity,sensor network,network performance,polynomial time approximation scheme,routing
Wireless network,Computer science,Network packet,Quality of service,Computer network,Schedule,Time complexity,Wireless sensor network,Computational complexity theory,Distributed computing,Network performance
Journal
Volume
Issue
ISSN
10
10
1536-1233
Citations 
PageRank 
References 
3
0.39
21
Authors
5
Name
Order
Citations
PageRank
Qiao Xiang1749.11
Hongwei Zhang293567.71
Jin-hong Xu3112.70
Xiaohui Liu4443.34
Loren J. Rittle51106.15