In the third of a four part series on implementation of wireless sensor networks, the authors of “ Ad hoc wireless networks ” go into detail about the techniques needed in the sensor nodes to discover their location and the specialized MAC protocols that need to be developed or modified.
The objective of the data-gathering problem is to transmit the sensed data from each sensor node to a base station (BS). One round is defined as the BS collecting data from all the sensor nodes once. The goal of algorithms which implement data gathering is to maximize the number of rounds of communication before the nodes die and the network becomes inoperable.
This means minimum energy should be consumed and the transmission should occur with minimum delay, which are conflicting requirements. Hence, the energy delay metric is used to compare algorithms, since this metric measures speedy and energy-efficient data gathering. A few algorithms that implement data gathering are discussed below.
Direct Transmission. All sensor nodes transmit their data directly to the BS. This is extremely expensive in terms of energy consumed, since the BS may be very far away from some nodes. Also, nodes must take turns while transmitting to the BS to avoid collision, so the media access delay is also large. Hence, this scheme performs poorly with respect to the energy delay metric.
Using PEGASIS for sensor information collection
Power-efficient gathering for sensor information systems (PEGASIS)  is a data-gathering protocol based on the assumption that all sensor nodes know the location of every other node, that is, the topology information is available to all nodes.
Also, any node has the required transmission range to reach the BS in one hop, when it is selected as a leader. The goals of PEGASIS are as follows:
1. Minimize the distance over which each node transmits
2. Minimize the broadcasting overhead
3. Minimize the number of messages that need to be sent to the BS
4. Distribute the energy consumption equally across all nodes
A greedy algorithm is used to construct a chain of sensor nodes, starting from the node farthest from the BS. At each step, the nearest neighbor which has not been visited is added to the chain. The chain is constructed apriori, before data transmission begins, and is reconstructed when nodes die out.
Click on image to enlarge.
At every node, data fusion or aggregation is carried out, so that only one message is passed on from one node to the next. A node which is designated as the leader finally transmits one message to the BS.
Leadership is transferred in sequential order, and a token is passed so that the nodes know in which direction to pass messages in order to reach the leader. A possible chain formation is illustrated in Figure 12.8 above . The delay involved in messages reaching the BS is O(N ), where N is the total number of nodes in the network.
This is also a chain-based scheme like PEGASIS, which classifies nodes into different levels. All nodes which receive messages at one level rise to the next . The number of nodes is halved from one level to the next.
Click on image to enlarge.
For instance, consider a network with eight nodes labeled s0to s7. As Figure 12.9 above shows, the aggregated data reaches the BS in four steps, which is O(log2N ), where N is the number of nodes in the network. This scheme is possible when nodes communicate using CDMA, so that transmissions of each level can take place simultaneously.
Chain-Based Three-Level Scheme
For non-CDMA sensor nodes, a binary scheme is not applicable. The chain-based three-level scheme addresses this situation, where again a chain is constructed as in PEGASIS. The chain is divided into a number of groups to space out simultaneous transmissions in order to minimize interference. Within a group, nodes transmit one at a time. One node out of each group aggregates data from all group members and rises to the next level.
The index of this leader node is decided apriori. In the second level, all nodes are divided into two groups, and the third level consists of a message exchange between one node from each group of the second level. Finally, the leader transmits a single message to the BS. The working of this scheme is illustrated in Figure 12.10 below.
Click on image to enlarge.
The network has 100 nodes, and the group size is ten for the first level and five for the second level. Three levels have been found to give the optimal energy × delay through simulations.
MAC protocols for sensor networks
MAC protocols in sensor networks must create a network infrastructure to establish communication links among the thousands of randomly scattered sensors. It must also ensure fair and efficient sharing of communication resources among the nodes, so that the overall lifetime of the network can be maximized.
The challenges posed by sensor network MAC protocols make them distinct from other wireless based networks. Unlike infrastructure-based cellular networks, there is no single controlling authority in sensor networks, so global synchronization becomes difficult.
Power efficiency is of utmost concern in sensor networks. They also encounter frequent topology changes due to mobility and failure. These factors emphasize the need for MAC protocols specific to sensor networks.
There are three basic kinds of MAC protocols used in sensor networks: fixed-allocation, demand-based, and contention-based. Fixed-allocation MAC protocols share the common medium through a predetermined assignment.
They are appropriate for sensor networks that continuously monitor and generate deterministic data traffic, since all nodes which have been allotted the channel can make use of their slot in each round. Fixed-allocation protocols provide a bounded delay for each node.
However, in the case of bursty traffic, where the channel requirements of each node may vary over time, a fixed allocation may lead to inefficient usage of the channel.
Demand-based MAC protocols are used in such cases, where the channel is allocated according to the demand of the node. Though they require the additional overhead of a reservation process, variable rate traffic can be efficiently transmitted using demand-based MAC protocols.
Finally, the contention-based MAC protocols involve random-access-based contention for the channel when packets need to be transmitted. They are again suitable for bursty traffic, but there is a possibility of collisions and no delay guarantees can be provided. Hence, they are not suitable for delay-sensitive or real-time traffic. Some of the popular sensor network MAC protocols have been briefly described in the next section.
Self-Organizing MAC for sensor MACs and EAR
Self-organizing MAC for sensor (SMACS) networks and eavesdrop and register (EAR) are two protocols which handle network initialization and mobility support, respectively. SMACS is a distributed protocol for network initialization and link-layer organization . In this protocol, neighbor discovery and channel assignment take place simultaneously in a completely distributed manner.
A communication link between two nodes consists of a pair of time slots, at a fixed frequency, which is randomly chosen at the time of establishing the link. Such an assignment is possible in sensor networks without interference from neighboring nodes because the available bandwidth is much larger than the data rate required for a message transmission between two nodes.
This scheme requires synchronization only between communicating neighbors, in order to precisely define the slots to be used for their communication. Power is conserved by turning off the transceiver during idle slots, and using a random wake-up schedule during the network start-up phase.
The EAR protocol enables seamless connection of nodes under mobile and stationary conditions. This protocol makes use of certain mobile nodes, besides the existing stationary sensor nodes, to offer service to maintain connections.
Mobile nodes eavesdrop on the control signals and maintain neighbor information. The mobile nodes assume full control over connections and can drop connections when they move away. Mobility is hence made transparent to SMACS, since it is independently handled by EAR.
This is a centrally controlled scheme which assumes that nodes communicate directly to a nearby BS. A pure TDMA scheme minimizes the time for which a node has to be kept on, but the associated time synchronization costs are very high. A pure FDMA scheme allots the minimum required bandwidth for each connection.
The hybrid TDMA/FDMA scheme, proposed in , uses an optimum number of channels, which gives minimum overall power consumption. This is found to depend on the ratio of power consumption of transmitter to receiver. If the transmitter consumes more power, a TDMA scheme is favored, since it can be switched off in idle slots to save power.
On the other hand, the scheme favors FDMA when the receiver consumes greater power. This is because, in FDMA, the receiver need not expend power for time synchronization by receiving during the guard band between slots, which becomes essential in a TDMA scheme.
CSMA-Based MAC Protocols
Traditional CSMA-based schemes are more suitable for point-to-point stochastically distributed traffic flows. On the other hand, sensor networks have variable but periodic and correlated traffic . A CSMA-based MAC protocol for sensor networks has been described in .The sensing periods of CSMA are constant for energy efficiency, while the back-off is random to avoid repeated collisions.
Binary exponential back-off is used to maintain fairness in the network. An adaptive transmission rate control (ARC) is also used, which balances originating and route-through traffic in nodes. This ensures that nodes closer to the BS are not favored over farther nodes.
ARC uses linear increase and multiplicative decrease of originating traffic in a node. The penalty for dropping route-through traffic is higher, since energy has already been invested in making the packets reach until that node. ARC performs phase changes, that is, it staggers the transmission times of different streams so that periodic streams are less likely to collide repeatedly. Hence, CSMA based MAC protocols are contention-based and are designed mainly to increase energy efficiency and maintain fairness.
The location information of sensors has to be considered during aggregation of sensed data. This implies each node should know its location and couple its location information with the data in the messages it sends. A low-power, inexpensive, and reasonably accurate mechanism is needed for location discovery.
A global positioning system (GPS) is not always feasible because it cannot reach nodes in dense foliage or indoors. It also consumes high power and makes sensor nodes bulkier. Two basic mechanisms of location discovery are now described.
Indoor Localization. Indoor localization techniques  use a fixed infrastructure to estimate the location of sensor nodes. Fixed beacon nodes are strategically placed in the field of observation, typically indoors, such as within a building.
The randomly distributed sensors receive beacon signals from the beacon nodes and measure the signal strength, angle of arrival, and time difference between the arrival of different beacon signals. Using the measurements from multiple beacons, the nodes estimate their location.
Some approaches use simple triangulation methods, while others require apriori database creation of signal measurements. The nodes estimate distances by looking up the database instead of performing computations. However, storage of the database may not be possible in each node, so only the BS may carry the database.
Sensor Network Localization
In situations where there is no fixed infrastructure available and prior measurements are not possible, some of thesensor nodes themselves act as beacons. They have their location information, using GPS, and these send periodic beacons to other nodes.
In the case of communication using RF signals, the received signal strength indicator (RSSI) can be used to estimate the distance, but this is very sensitive to obstacles and environmental conditions.
Alternatively, the time difference between beacon arrivals from different nodes can be used to estimate location, if RF or ultrasound signals are used for communication. This offers a lower range of estimation than RSSI, but is of greater accuracy.
Localization algorithms require techniques for location estimation depending on the beacon nodes’ location. These are called multi-lateration (ML) techniques. Some simple ML techniques are described in what follows :
Atomic ML: If a node receives three beacons, it can determine its position by a mechanism similar to GPS. This is illustrated in Figure 12.11 above.
Iterative ML: Some nodes may not be in the direct range of three beacons. Once a node estimates itslocation, it sends out a beacon, which enables some other nodes to now receive at least three beacons. Iteratively, all nodes in the network can estimate their location. Thisis shown in Figure 12.12 below.
Clickon image to enlarge.
The drawback of this multi-hop method is that errors are propagated, hence estimation of location may not be accurate.
Collaborative ML: When two or more nodes cannot receive at least three beacons each, they collaborate with each other. As shown in Figure 12.13 below, node A and node B have three neighbors each. Of the six participating nodes, four are beacons, whose positions are known. Hence, by solving a set of simultaneous quadratic equations, the positions of A and B can be determined.
A directionality-based localization approach has been used which assumes that beacon nodes have broadcast capability to reach all nodes of the network, and a central controller rotates the beacons with a constant angular velocity in radians/s.
A constant angular separation is maintained between the beacon nodes. Nodes in the network measure the angles of arrival of beacon signals to estimate their location. The errors in this technique occur due to non-zero beam-width from the beacons. The beam is not a straight line as theoretically imagined, but it has a finite width. Hence, the measurement of the angle of the beacon signal will be inaccurate.
An shortest distance algorithm , which derives the location of sensor nodes based mainly on information about connectivity between nodes uses an all-pairs shortest paths approach on the network graph and has edges indicating connectivity between nodes.
Hence, the shortest distance between each pair of nodes is obtained. A mathematical technique called multi-dimensional scaling (MDS) is used to assign locations to nodes such that the distance constraints are satisfied.
The obtained picture of the network could be a rotated or flipped version of the actual network. If the actual positions of any three nodes in the network are known, then the entire network can be normalized (rotated or flipped to obtain a very accurate location of all other nodes.
C. Siva Ram Murthy received a B.Tech degree in electronics and communications engineering from the National Institute of Technology, an M.Tech degree in computer engineering from the Indian Institute of Technology, and a Ph.D in computer science from the Indian Institute of Science. He has to his credit over 100 research papers in international journals and conference publications as well as author of several text books on parallel computing, real time systems and networks, and optical networks. His research interest include parallel and distributed computing, real time systems lightwave networks, and, of course, wireless sensor networks.
B.S. Manoj is the recipient of an M.Tech degree in Electronics and Communications engineering from the Institution of Engineers in India. His research interest include ad hoc wireless networks, next generation wireless architectures and wireless sensor networks.
This series of articles is from the book “Ad Hoc Wireless Networks ,” by C. Siva Ram Murthy and B.S. Manoj, Copyright 2011, used by permission of PearsonEducation, Inc.. Written permission from Pearson Education, Inc. is required for all other uses.