Search

Minimum-Latency Aggregation Scheduling (MLAS) has been well studied when all the networking nodes are always active. However, it is well-known that the nodes often switch between the active state and the sleep state to save energy. A node in duty-cycled scenarios with active/sleep cycles may require transmitting multiple times to send the message to all of its neighbors due to their different active times. MLAS in multihop wireless networks with Duty-Cycled scenarios (MLASDC) has also been well-studied under graph-based interference models such as the protocol interference model. To the best of our knowledge, no approximation algorithms have been proposed for MLASDC subject to physical interference. This is the first paper to develop efficient approximation algorithms for MLASDC subject to physical interference. The data aggregation schedule produced by our algorithm proposed in this paper achieves an approximation ratio at most a constant time of the length of a scheduling period if the maximum degree Δ of the network is bounded.

Many applications of wireless sensor networks (WSNs) are time-critical as well as requiring secure operations, and have serious consequences if the network is compromised. WSNs are often deployed in hostile environments where communication is monitored and the sensor nodes are subject to be compromised or manipulated by adversaries. For such WSNs, it is very important to have secure communications among the sensors. The m-composite key pre-distribution schemes proposed in [3] is one of the most popular mechanisms for communication security of WSNs. With such a security scheme, two nodes within each other's transmission range have a secure link between them if their key rings have at least m keys in common. In this paper, we develop an efficient scheduling algorithm for data gathering on secure WSNs. The link between two nearby sensors may not be secure and cannot be used for communication. Such a nature of secure WSNs makes the analysis of any scheduling algorithm for gathering much more challenging than on WSNs that can be modeled as disk graphs. To the best of our knowledge, this is the first paper that develops fast gathering schedules for multihop WSNs where the network topology cannot be modeled as a disk graph.