Virtual Backbone Construction Algorithms Based on Protocol Interference Model
Interference is one of the main challenges in designing energy efficient protocols for wireless sensor networks. Decreasing interference can reduce energy consumptions of nodes and prolong the lifetime of the network. Combining graph matching and the prot
- PDF / 181,833 Bytes
- 10 Pages / 439.363 x 666.131 pts Page_size
- 25 Downloads / 179 Views
Abstract. Interference is one of the main challenges in designing energy efficient protocols for wireless sensor networks. Decreasing interference can reduce energy consumptions of nodes and prolong the lifetime of the network. Combining graph matching and the protocol interference model, in this paper, we propose a Matching Based Interference-Aware Dominating Set Construction Algorithm (MBIDSC), in which we consider a connected dominating set as a virtual backbone. The upper bounds of message complexity of the algorithm is O(nrΔ) and the time complexity is O(rΔ). Where n is the total number of nodes, Δ is the maximum degree of the network, r is the round of the algorithm, and d is the diameter of the network. We show the correctness of the algorithms and complexity of time and message by theoretical analysis. To the best of our knowledge, the proposed algorithm is the first results for the protocol interference model based on graph matching. Keywords: wireless sensor network, dominating set, virtual backbone, graph matching, interference.
1
Introduction
A wireless sensor network (WSN) consists of lots of mobile sensor nodes equipped with many radio communication devices, such as RF transceivers. Sensor nodes perform sensing, processing and communication tasks. In recent years, wireless sensor networks have been widely applied in various fields and deployed for many kinds of applications. Since WSNs can be quickly distributed in some geographical areas where humans fail to arrive, they play an important role in many fields, such as habitat monitoring, health care, military surveillance, target tracking, disaster relief and so on. Since sensor nodes are powered by batteries which reserve limited energy and can not be recharged, every node only communicates with nodes within its transmission range. Nodes fail to directly communicate with each other, if the Euclidean distance between them is larger than their transmission range. Therefore, their communication is dependent on other nodes (usually called relay nodes) within their transmission range, if there
Corresponding author.
L. Sun, H. Ma, and F. Hong (Eds.): CWSN 2013, CCIS 418, pp. 31–40, 2014. c Springer-Verlag Berlin Heidelberg 2014
32
G. Yan et al.
are such relay nodes. In a word, communication among nodes in WSNs may be single hop or multiple hops. WSNs usually are assumed to be homogeneous and work for certain time, since energy conservation is one of the essential issues in every research field of WSNs. In normal case, topology control in WSNs can perform the task to prolong the lifetime of the networks. Given a connected network graph, topology control is considered to compute a subgraph with specific required properties, such as connectivity, sparsity, low interference and so on. Dominating sets based on clustering are always used in topology controls. The great flexibility is the best advantage of a WSN, and the worst disadvantage of such networks is their lack of infrastructure. The disadvantage results in many difficulties in their applications. For
Data Loading...
