Coverage In Wireless Sensor Networks Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Most of the literatures concerning coverage in wireless sensor networks, deal with area coverage. Energy-efficient coverage techniques are important with respect to sensor networks, as they can extend the network lifetime. There are many generalized approaches in extending the lifetime of sensor networks while ensuring coverage. One of these techniques is to schedule node activity and put some nodes into sleep mode. Although the toughest challenge in this process is how to select nodes to put them into sleep mode.

2.1 Literature Survey

2.1.1 Power efficient organization of wireless sensor networks, S. Slijepcevic and M. Potkonjak, Proc. IEEE Int. Conf. Commun., 2, 472-476, Helsinki, Finland, June 2001 [15].

Slijepcevic and Potkonjak in [15] have taken a randomly deployed sensor network, which is divided into fields. According to them each sensor covers more one or more than one field and each filed has to be covered by at least one sensor. Sensor nodes are divided into covers, where each cover is a set of disjoint set of sensors. The goal of this is paper is to maximize the cardinality of the set of covers because it has a great impact on network lifetime. This has been achieved by the maximally constrained - minimally constraining heuristic. According to them fields are set of points where a two points belong to the same field if and only if they are covered by same set of sensors. The objective is to select these disjoint sets effectively while set the other nodes into sleep mode. Here fields are defined in such a way that, every point within a field is covered by the same set of sensor. Authors have devised the maximally constrained-minimally constraining algorithm which chooses the disjoint sets successively and gives priority to nodes which cover the critical element, covers high number of uncovered fields,

2.1.2 A coverage-preserving node scheduling scheme for large wireless sensor networks, D. Tian and N.D. Georganas, Proc. 1st ACM Workshop Wireless Sensor Networks and Applications, pp. 32-41, 2002 [16].

The main objective of the work in [16] is to minimize the number of working nodes in a network. Idea is to calculate node's sensing area and then compute the union of sensing areas of its neighbors. If the unions of sensing areas of neighbors cover the sensing area of a particular node, then the node can be turned off, while maintaining full coverage. The off-duty eligibility rule is expressed as: , which means the union of neighbors sensing areas is a superset of node i's sensing area. Two methods have been used to decide the off-duty eligibility rule. In the first method it is assumed that each node has same sensing range and they know their geographical location. While in the second method nodes have different sensing range due to two reasons; nodes have different sensing ranges from the beginning and their sensing range changes over time. Here the operation is divided into rounds: first phase is called self-scheduling stage, where nodes are selected based upon the off-duty eligibility rule and in the next phase non-eligible nodes in the self-scheduling phase starts the sensing process. Sensing phase is much longer than the self-scheduling phase to decrease energy consumption. Most important phase is the self-scheduling phase which is divided into two sub-phases. Objective of the first phase is to obtain neighbor information. Here nodes at the start of each round send a Position Advertisement Message (PAM) which incorporates nodes' ID and its current location information. To minimize energy consumption each node sends the PAM message with minimum power so that it reaches nodes within the sensing range of sender, as those nodes are only eligible for off-duty rule. If variable sensing range used, in that case sensing range is also included in the PAM message. After obtaining the position information, each node calculates the sponsored coverage and in effect decided whether it is eligible for off-duty or not. If all the nodes start to determine the eligibility at the same time, there is a chance of blind point to occur, where it is the point which is not covered by any sensor node. To get rid of this situation node start its determination after a random back-off time Td and broadcasts a Status Advertisement Message to let other nodes know its status. Neighboring nodes after hearing the SAM purge all the information of the sender node from their table. Authors have assumed a back-off window of size W. Even if this window is quite large, there is a considerable chance that two nodes might start the process with probability 1/W. To counter this fact nodes wait a short amount of time Tw after sending SAM, instead of switching of the transmitter immediately after finding itself eligible.

Reference [16].jpg

Fig. 1. FSM for self-scheduling phase

2.1.3 Energy efficient robust sensing coverage in large sensor Networks, F. Ye, G. Zhong, S. Lu, and L. Zhang, Technical Report, UCLA, 2002.

In [17] a node density control strategy has been taken to ensure complete coverage. Here each node can in one of three states: sleeping, wakeup and working. Working nodes do the sensing and communication task. While sleeping and wakeup state nodes ensure the replacement of dying working nodes due to energy depletion. Sleeping nodes wake up after an exponentially distributed time defined by the wakeup rate . After waking up sleeping nodes send a probing message PRB within a range r. All the working nodes within range r will reply back with PRB_RPY message after hearing the PRB message. The sleeping node which sent the PRB message will in response to the PRB_RPY message go to the sleep mode once again. If the wakeup node does not hear any PRB_RPY message within a specified time interval Tw, then it will continue to work as a working node. Authors have showed that by carefully choosing the value of r and , it is possible to obtain a desirable node density p.

Another important concept related to coverage is "connected random coverage". Connectivity is an important issue in wireless sensor network which ensures that any node in a network can send message to any other node, which subsequently is delivered to the sink or base station. Authors have addressed an

objective to determine the minimal set of nodes in any sensor network which can provide both coverage and connectivity. Several approaches have been taken to ensure both.

2.1.4 Maintaining sensing coverage and connectivity in large sensor networks, H. Zhang and J.C. Hou, technical report UIUC, UIUCDCS-R-2003-2351, June 2003 [18]

Zhang and Hou in [18] have showed that if the communication range Rc is at least twice as large as sensing range Rs, then the complete coverage of the underlying network will ensure complete connectivity among the working nodes. When communication range Rc is at least as large as sensing range Rs, then to ensure complete coverage, there has to be at least one intersection between the sensing range of two sensor nodes and that intersection has to be covered. Based on these observations authors have proposed a distributed, localized algorithm called Optimal Geographic Density Control. Here the algorithm is divided into rounds. At the beginning of each round some of the starting nodes are selected as the working node. After a back-off time a starting node broadcasts a power-on message and switches its state to ON. This power-on message incorporates location information of the starting node and the direction in which the next working node will be selected. Random selection of starting nodes in each round ensures that energy consumption among nodes will be uniform. At the start of each round all the nodes are in UNDECIDED state, during the execution of the rounds they change their state to ON or OFF state depending upon the selection of working nodes. After receiving a power-on message a node checks to see if its sensing area is covered by its neighbors or not with the help of the neighbor information list. If its sensing area is covered, then it will go to the OFF state. A node will switch its state to ON state, if it is closest to the optimal geographical location of a working sensor node which covers the crossing of two current working nodes.

2.1.5 Integrated coverage and connectivity configuration in wireless sensor networks, X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C.D. Gill, Proc. First ACM Conf. Embedded Networked Sensor Syst. (SenSys'03), pp. 28-39, Nov. 2003 [19].

The work in Wang described in [19] introduces Coverage Configuration Protocol (CCP) which provides a certain degree of coverage based upon the request of the application. Nodes are required to compute the coverage of intersection points, to do this they maintain neighbor information list. A node can be in one three states: SLEEP, LISTEN and ACTIVE. All the nodes start in SLEEP state. After some

time when a node is in the LISTEN state, it computes the eligibility criteria to switch itself to either SLEEP or ACTIVE state. When a node is in the ACTIVE state, it continually evaluates the eligibility criteria whenever it receives the HELLO message and either remains in the ACTIVE or switches to SLEEP state.

2.1.6 A Probabilistic Coverage Protocol for Wireless Sensor Networks, Mohamed Hefeeda, Hossein Ahmadi, Proceeding WCNC'09 Proceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference [20].

Hefeeda and Ahmadi in [20] have described the Probabilistic Coverage Protocol (PCP) which assures to provide complete coverage. They assure that each of the point in a monitored area is covered by at least one sensor. In PCP, a node can be in one of four states: ACTIVE, SLEEP, WAIT, or START. In the beginning of each round all the nodes set its state to START and select a random timer Ts proportional to its remaining energy. Node with the smallest timer becomes the activator node. This activator node send activation message within its communication range, stating it's coordinate. Nodes within the communication range of the activator node will activate themselves and switch to the ACTIVE node, if they are situated at the vertices of the hexagon centered at the activator node. Nodes within the hexagon put themselves into sleep mode. A node will decide to activate itself if the angle of arrival of the advertisement message is and the distance from the activator node is s, after that the node will become next activator node and all other will go to sleep state.

2.1.7 Yi Zou, Krishnendu Chakrabarty, "A Distributed Coverage and Connectivity Centric Technique for Selecting Active Nodesin Wireless Sensor Networks", IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 8, AUGUST 2005 [21].

In [21] Chakrabarty and Zou proposed CCANS or Coverage Centric Active Node Selection algorithm. The objective of this algorithm is to form a connected dominating set forming a backbone of connected nodes that can completely cover the whole sensor network region. Nodes can be in one of three states: ACTIVE, SLEEP and UNSET. When algorithm starts, nodes are in the UNSET state. In ACTIVE state nodes can have multiple configurations; only sensing unit on, only communication unit on and both

sensing and communication unit on. Algorithm is divides in two rounds: sensing coverage calculation and connectivity checking. Prior to the start of the algorithm nodes gather local information; immediate one-hop neighbor nodes, their location etc. Algorithm takes a token based approach. Node 0 initiates this algorithm and initially posses the token. Node holding the token at a particular moment is called the token node and other nodes listen to this node and perform actions. In the first stage of the algorithm token node calculates the coverage redundancy and decides whether to change its state or not. If a node sees its sensing area is covered by other nodes, then it will move to SLEEP state otherwise it will move to ACTIVE state. When a node changes its state, it sends the token to its neighbor nodes. Neighbor nodes decide accordingly. When the last UNSET nodes decision making is complete then the next stage of the algorithm starts. The next phase of the algorithm checks the state assignment and network connectivity. In these process nodes once again check its coverage redundancy and if any errors are found then those are corrected in terms of changing the states. After correcting states based upon coverage redundancy calculation, nodes will check network connectivity. If a node with SLEEP state sees that its neighbor nodes are in ACTIVE state, but not connected, then it will change its state to ACTIVE state. Authors have also proved that if the communication radius is at least as large as the sensing radius then full network connectivity is implied.

Another recent measurement of coverage in wireless sensor network is in terms of assuring QoS. This concept was first described by Meguerdichian in [3]. Recent literatures are converging towards this formulation of coverage. QoS coverage deals with the fact that depending on the application and nature of terrain, formulation and meaning of coverage is subject to change. It might possible that for some applications we are rather interested in checking the coverage status at a particular region in the network or we want to deploy large number of nodes at a particular area for minimizing the possibility of any critical event getting undetected. Ex. If we deploy sensor nodes to detect chance of tsunami, then we might be interested to vary the number of deployed sensors depending upon the geographical importance. Next chapter will discuss the basis of my proposed QoS coverage algorithm along with the survey of related literatures.

2.2 Tool Study

2.2.1 Castalia 3.2:

Castalia simulator [22] is specifically built for the simulation purpose of Wireless Sensor Networks, Body area Networks etc. It was developed at NICTA, Australia and specially targeted for distributed and centralized algorithms for these type of networks. One of the main features of Castalia is its almost realistic wireless and radio characteristics. Castalia is built on top of OMNet++ simulator, using its modular architecture; it retains the basic architecture of OMNet++ and has some added features on top of that. Simulators are indeed an important platform for testing WSN applications before using them in real networks; Castalia offers the required algorithm validation for these applications.

OMNet++ simulation engine is based on simple modules. These are basic building block of the simulator Compound modules contain submodules or multiple simple modules. OMNet++ model or network consists of a hierarchy of modules nested together. Modules communicate through message passing mechanism and they are connected through gates. An OMNet++ network or model is described by NED language, which is specifically built for OMNet++. Message are the only medium through which modules communicate, they use complex data structures. Message can be packets or frames in a communication network or package arrival in a manufacturing process. Messages can go to the destination directly or through some intermediate modules. Modules can receive messages from other modules or from within that module itself. Gates are the interface through which modules communicate. Several parameters are defined in for the module either in the NED file or in the network configuration file omnetpp.ini. Castalia uses these basic properties of OMNet++ to build the simulation platform specially geared for wireless sensor network.

2.2.2 The Distribution:

The Castalia 3.2 distribution has the following directory structure:

\bin: Scripts of Castalia, CastaliaResults and CastaliaPlot

\out: Object files of the compiled code

\Simulations: Simulation results and network configuration files


\helpStructures: Main Castalia C++ files

\node: Modules relevant to a node

\application: Contains modules for sensor application layer protocols

\communication: Contains radio, MAC and Routing Submodules

\mobilityManager:Modules defining node's demographical charecteristics

\resourceManager: Module declaring node's basic resources

\sensorManager: This module connects to the wireless channel for sampling

\physicalProcess: It simulates a physical process that could be measured/sample by the sensor node

\wirelessChannel: The wireless channel module simulates the wireless medium and describes its various characteristics.

2.2.3 Installing Castalia:

Castalia 3.2 requires OMNet++ 4.0 or 4.1. OMNet++ can be used either in Windows or Linux. Although Castalia is supported only in Linux. I have used Ubuntu 10.10 linux distribution for my simulation purpose.

Installing OMNet++: After Downloading the OMNet++4.1.tar.gz package from OMNet++ website following steps were followed:

$ tar xvfz omnetpp-4.1-src.tgz

$ export PATH=$PATH:~/omnetpp-4.1/bin

$ export LD_LIBRARY_PATH=~/omnetpp-4.1/lib

$ cd omnetpp-4.1/

$ ./configure

$ make

Installing Castalia: Downloaded the source code of Castalia named Castalia-3.2.tar.gz from After that these steps are followed:

$ tar -xvzf Castalia-3.2.tar.gz

$ cd Castalia-3.2/

$ ./makemake


Building Castalia for My Source Code: It is possible to include any additional source code within Castalia directory for implementation purpose without violating the required directory structure. For the implementation of my algorithm, I have created a new module in the directory /Castalia-3.2/src/node/application/coverageTest. This module contains the, CoverageTest.h, CoverageTest.ned and CoverageTest.msg files.

To rebuild Castalia the following simple steps are performed:

$ make clean

$ ./makemake

$ make

2.2.4 Structure of Castalia:

Castalia is built upon the generic concept of modules which is the basic building block of OMNet++. Sensor nodes are visualized as composite modules which do not interact among themselves directly. Nodes directly communicate with Wireless Channel and Physical Process through message passing. Through wireless channel nodes decide to which node packets to be sent. Nodes communicate to the Physical process module for sensing purpose. There could be multiple physical processes leading to multiple sensing devices. Node module is a composite one and is the most important. It interacts with almost all the other simple and composite modules. Modules are defined with the help of NED language. Through NED language module name, parameters, interfaces and sub-module structures are defined. Every module is represented as a directory, if it's a composite module then it will contain sub-directories or if it's a simple module then it will have C++ files, describing the behavior of the module in which it is described in.

2.2.5 Modeling in Castalia:

This part explains how different composite modules of Castalia have been modeled. Among all of the modules communication and radio module has been designed with more preciseness.

Wireless Channel:

In terms of wireless channel characteristics Castalia authors claim that it is the most "realistic simulator" for simulation purpose of wireless sensor network. The realistic nature of this simulator lies in the fact that the wireless channel module has

been designed including specific parameters and input files which simulates the idealistic behavior. The configurable parameters can be tuned to simulate any wireless channel characteristic.

Average Path Loss Modeling:

One of the important features of Castalia is how it measures average path loss between two sensor nodes or between two points in space. Castalia uses lognormal shadowing model to estimate average path loss, which gives more realistic physical layer scenario in comparison to other path loss models. In lognormal shadowing average path loss is estimated based on the following equation:


PL(d) is the path loss at a point d. PL(d0) is path loss at a known reference point d0. Path loss exponent is defined by η. Xσ is a gausean random variable with standard deviation σ. These parameters are defined in the /wirelessChannel/WirelessChannel.ned file in the wireless channel module.

Delivering Signals to the Radio Module:

Wireless Channel directly passes the signal to the radio module. Radio module then calculates SINR (Signal to Noise plus Interference Ratio) and interference to make the decision whether to accept the packet or not. Not all the messages are delivered to the radio module, a parameter called signal strength

threshold decides whether a signal from the wireless channel will be delivered to the radio module or not.

The Radio:

Radio module is one of the most important part of this simulator, as it largely emulates a real time behavior. This module is highly configurable and can be used to create multiple radio behaviors. Some of the distinct characteristics of this module are:

Three radio states are available with this module. These are; TRANSMIT, RECEIVE and SLEEP. SLEEP state can be configured to produce multiple SLEEP state behavior.

Different transition delays are defined for transitions form one state to another.

Multiple modulation techniques are defined in Castalia; PSK, FSK, QPSK, DPSK etc.

Multiple mode of operations can be defined using several configurable parameters; such as, data rate, bandwidth, noise floor etc.

TRANSMIT state use multiple power levels.

Continuous RSSI value calculation is done by the radio module.

MAC Module:

MAC module is responsible several channel aces related tasks and important part of any simulator. Castalia's MAC module outperforms its counterpart of any other simulator. Five different MAC protocols are defined in this module; Tunable

MAC, TMAC, SMAC, IEEE 802.15.4 and IEEE 802.15.6. Among these only Tunable MAC, TMAC and SMAC are used for wireless sensor networks.

Tunable MAC:

Tunable MAC is a contention based MAC protocol. It assumes broadcast kind of network and doesn't use acknowledgements, RTS and CTS packets. It is a CSMA like protocol and depends largely on a duty-cycle based approach. Important parameters relevant to this module are described below:

Dutycycle is the parameter which defines the amount of time a node will keep listening to the wireless channel. This parameter affects the energy consumption a great deal.

Listeninterval defines the amount of time a node stays on listening.

T-MAC and S-MAC:

TMAC is considered as the de-facto standard for MAC module in any simulator. Castalia uses this module to simulate MAC module behavior. One of the many advantages of TMAC is its low energy consumption (due to high amount of duty-cycling and time synchronization) and high packet delivery ratio. TMAC's duty cycle is highly adaptive and that that leads to a better performance. SMAC is created using same module of TMAC by changing only some of the parameters. SMAC is the predecessor version of TMAC which uses a inflexible duty-cycle scheme. Parameters of this module are defined in src/node/communication/mac/tMac/TMAC.ned. Some of the important parameters of this module are:

maxTxRetries defines as the number of transmission attempts taken by a MAC module to a destination.

contentionPeriod is the contention interval defined to avoid interference among neighbor nodes.

listenTimeout is the amount of time a node will listen to the channel before going into SLEEP mode.


Routing module is one of the areas where authors expect improvement. Currently the routing module provides two routing sub-modules; multipathRingsRouting and bypasssRouting. BypassRouting protocol doesn't use routing and nodes bypass the routing module. MultipathRingsRouting is a multipath routing method; a packet sent from originating node takes multiple paths to the sink node.

Chapter -3

GUR Algorithm and related study

This chapter introduces the GUR optimization algorithm and its related study. GUR is a well known algorithm working on the basis of game theory. After describing the basic principles of GUR game, it will be observed how GUR game can be mapped in wireless sensor networks. Till now limited amount of work has been done in the domain of sensor network using GUR algorithm, some of these works will be discussed.

3.1 GUR Algorithm

In this section first I will discuss the basic concepts related to GUR algorithm, which forms the basis of it. GUR algorithm is based on the biased random walk behavior in finite state automata and it also inherits the basic principles of game theory. Random walk behavior over a linear set of points will be discussed first followed by basic principles of game theory.

3.1.1 Biased random walk behavior over FSA

In mathematical sciences random walk is a behavior when the direction of a trajectory is uncertain, which means it can take any direction at any time. Classic examples of random walk are Brownian motion, atoms traversing within molecules etc. Random walks can be visualized in 1D, 2D or in 3D planes. When the next step in any random walk is biased towards a certain possibility from set of possibilities then this type of behavior is called biased random walk. This is our interest with respect to the behavior of GUR algorithm.

In [23] authors proposed a method to describe the behavior of biased random walk over a set of linear array of points. For the sake of simplicity linear array of points can be visualized as the set of automaton states in a finite state automaton. In a typical finite state automata states

can make transition from any state to any other state depending on the characteristics of the transition function. They have assumed the linear array of points as {0, 1, 2, 3……., n}, where the endpoints 0 and n are called the trap points. In this model transition is only possible from a point to its immediate neighbor in either direction. If for instance the probability of transition from state x to x+1 is p then the probability of transition from x to x-1 is (1-p). If these transition probabilities vary then this system exhibits biased random walk behavior, because at any particular moment transition from any point to one of its immediate neighbor is biased, one of the transition holds higher probability than the other.

3.1.2 Game Theory

Game theory [24] is the study of both cooperative and conflicting behavior. It's a situation where one or more entities called agents interacts with a centralized entity for their individual and a collective objective of the system. These entities can be anything starting from human beings, groups or even sensor nodes. All those entities hold some strategies which help to maximize their benefit. Each of these entities has decision making capability independently and they make that decision in a greedy fashion to get the best outcome possible.

According to formal definition a game can be described by set of players {1,2,…, N}and set of strategies available to them. Players make use of these strategies and choose the best strategy at particular moment which is of their best interest. A player is assumed to be rational, which means he will take an action based on the expected behavior of his opponents that maximizes his profit or interest. The role of the central coordinator or referee is quite crucial with respect to game theory as it defines the behavior of the game in terms of setting the strategies and controlling the game.

3.1.2 GUR Game

The concept of GUR game was proposed by Kleinrock and Tung in [25] and it gives a framework to achieve self-optimization and self-control on the basis of simple game. In a typical distributed system achieving self-optimization and self-control is a challenging task In a distributed environment agents behave in a spontaneous and independent way to achieve some

objective. In this paper authors achieved distributed coordination through the use of finite state

automaton which is associated with each of the agents and which guide them. In some applications of distributed systems agents need to cooperate on a task which might be controlled from a central coordinator. In these systems agents are controlled by the external coordinator which issues commands to the system and agents are guided by the automaton associated with them. This system largely depends on the automaton behavior associated with each agent as it helps the system to converge towards the steady state.

Authors have proposed a simple with N number of players {1, 2, 3……, N} and a central coordinator called Referee. As already stated Referee controls this game and sends out control message to all of the agents to decide their action accordingly. One interesting fact here is that in this game neither of the agents know about its peers and nor can they predict the possible actions taken by them. At first Referee asks all the nodes to send yes or no votes to him. Referee after receiving these votes counts the number of yes votes. This number works as the basis of calculating a metric called reward function which will work as the feedback information to the agents. Base station broadcasts this reward function to all the agents which help them to form a distributed coordination. This reward function is the core part of GUR game as this value will help the agents to decide their actions.

Referee will calculate the reward value based upon the fraction of agents f who voted yes in the current iteration. Reward value ranges from 0 to 1. No player knows how his other peers have voted and will independently decide his action upon receiving the reward value from the referee. On receiving a reward value r from the referee agents rewards them with probability r and punishes them with probability (1-r). The characteristics of reward and punish behavior depends on the underlying finite state automaton associated with each of the agents. The reward and punish behavior doesn't depend on the vote results, agents will reward or punish themselves regardless of how they have voted. Following figure fig [] depicts the ideal behavior of a GUR reward function.