Approximation algorithm for data broadcasting in duty cycled multi-hop wireless networks
- PDF / 471,627 Bytes
- 14 Pages / 595 x 794 pts Page_size
- 101 Downloads / 235 Views
RESEARCH
Open Access
Approximation algorithm for data broadcasting in duty cycled multi-hop wireless networks Dianbo Zhao* and Kwan-Wu Chin Abstract Broadcast is a fundamental operation in wireless networks. To this end, many past studies have studied the NP-hard, broadcast problem for always-on multi-hop networks. However, in wireless sensor networks, nodes are powered by batteries, meaning, they have finite energy. Consequently, nodes are required to have a low duty cycle, whereby they switch between active and sleep state periodically. This means that a transmission from a node may not reach all of its neighbors simultaneously. Consequently, any developed broadcast protocols must consider collisions and the wakeup times of neighboring nodes. Henceforth, this paper studies the minimum latency broadcast scheduling problem in duty cycled multi-hop wireless networks (MLBSDC), which remains NP hard. The MLBSDC problem aims to find a collision-free schedule that minimizes the time in which the last node receives a broadcast message. We propose a novel algorithm called CFBS that allows nodes in different layers of the broadcast tree to transmit simultaneously. We prove that CFBS produces a latency of at most (T + 1)H + T O (log2 H). Here, T denotes the number of time slots in a scheduling period, and H is the optimal broadcast latency obtained from the shortest path tree algorithm assuming no collision. We also show that the total number of transmissions is at most 4(T + 2) times larger than the optimal value. The results from extensive simulation show that CFBS has a better performance than OTAB, the best broadcast 3 that of OTAB. scheduling algorithm to date. In particular, the broadcast latency achieved by CFBS is up to 20 1 Introduction Wireless sensor networks (WSNs) consist of numerous sensor nodes deployed in a field. These nodes are usually resource constrained in terms of battery lifetime and computation, and are equipped with a number of sensing elements. Moreover, they have one or more radios and communicate with each other via multi-hop communications because these radios have a bounded and short transmission range. In addition, there exist one or more sinks to collect sensed data and to issue commands that affect the operation of sensor nodes. To date, WSNs have found a myriad of applications. For example, precision agriculture [1], monitoring of pests [2], and volcanology [3] to name a few. Network-wide broadcast is a fundamental operation in wireless networks, where a message needs to be propagated from a source node, e.g., a sink, to all other *Correspondence: [email protected] School of Electrical, Computer & Telecommunications Engineering, University of Wollongong, Wollongong, 2500, Australia
nodes. It is relied upon by several network protocols, such as routing [4], information dissemination [5], and resource/services discovery [6]. These protocols in turn help applications in disaster relief, military communication, rescue operation, and object detection [7]. For these applications, time is cr
Data Loading...
