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.
on image to enlarge.
Figure 12.8. Data gathering with PEGASIS.
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.
on image to enlarge.
Figure 12.9. Binary scheme.
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.
on image to enlarge.
Figure 12.10. Chain-based three-level scheme.
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.