Open access

Efficient Node Placement for Congestion Control in Wireless Sensor Networks

Written By

Charalambos Sergiou and Vasos Vassiliou

Submitted: 12 November 2011 Published: 18 July 2012

DOI: 10.5772/48201

From the Edited Volume

Wireless Sensor Networks - Technology and Applications

Edited by Mohammad Matin

Chapter metrics overview

3,675 Chapter Downloads

View Full Metrics

1. Introduction

Wireless sensor nodes are small, embedded computing devices that interface with sensors/ actuators and communicate using short-range wireless transmitters. Such nodes act autonomously, but cooperatively to form a logical network, in which data packets are routed hop-by-hop towards management nodes, typically called sinks or base stations. A Wireless Sensor Network (WSN) comprises of a potentially large set of nodes that may be distributed over a wide geographical area, indoor or outdoor. Wireless Sensor Networks (WSNs) enable numerous sensing and monitoring services in areas of vital importance such as efficient industry production, safety and security at home as well as in traffic and environmental monitoring. Traffic patterns in WSNs can be derived from the physical processes that they sense. WSNs typically operate under light load and suddenly become active in response to a detected or monitored event. Early research studies in WSNs targeted military applications, especially for battlefield monitoring. In the last few years, due to the progress of low powered units and improvements in radio technologies, wireless sensor networks technologies have gained momentum. WSNs are now being deployed in civilian areas and being used for habitat observation ([1], [2]), health monitoring ([3]), object tracking ([4], [5]) etc. In addition, lately, there is an emergence of mission-critical applications ([6]).

Emergence of mission-critical and information demanding applications in WSNs renders performance control essential, for mission accomplishment. Heavy traffic load is a major factor that affects the performance of any type of network. The situation worsens in low- powered, unreliable WSNs. Thus, a prominent factor that under specific circumstances, can improve or deteriorate the performance of WSNs, can be the way that nodes are placed on the monitored field. Proper node placement is essential to ensure good sensing coverage and communication connectivity.

In this work we present and analyze four general ways that nodes can be placed on a grid and we compare the performance of a representative number of routing and congestion control algorithms under these placements.

The examined algorithms are ESRT ([7]), Sen- TCP ([8]), Directed Diffusion ([9]), HTAP ([10]) and Flooding. These algorithms are evaluated under four different placements. Simple Diffusion, Random, Grid and Biased- Random. Algorithms and placements are described in detail, in the next sections.

Initial results of this work have been presented in ([11] and [12]). In this paper we extent the number of evaluated algorithms in order to present a complete and solid work. Thus, we include an algorithm that represents the category of "reliable data transport" (ESRT), as well as a generic routing algorithm ("flooding"). Hence, in this paper, we provide representative results from all the categories of congestion control and reliable data transport algorithms in WSNs, under different placements.

Simulation results show that the performance of specific algorithms can be improved under specific placements. In particular, algorithms that employ multiple or alternative paths for forwarding the excess traffic from source to sink are favored by specific placements.


2. Related work

Several node placements have been proposed in literature concerning WSNs.

Younis et al ([13]) present a survey for strategies and techniques for node placements in WSNs and provide a categorization of the placement strategies into static and dynamic, depending on whether the optimization is performed at the time of deployment or while the network is operational.

Toumpis et al ([14]) provide an optimal deployment of large wireless sensor networks so as to minimize the number of nodes that is needed in order to transmit data from multiple sources to multiple sinks.

In ([15]) authors evaluate the tolerance against both random failure and battery exhaustion from the viewpoint of stochastic node placement. They consider three typical types of stochastic sensor placement: Simple diffusion, Constant Placement and R- Random placement.

In ([16]) authors studied the problem of determining the critical node density for maintaining k-coverage of a given square region. They have considered three different deployment strategies: Poisson point process, uniform random distribution and grid deployment and have shown that the two random strategies have identical density requirements for k-coverage. They also showed that grid deployment requires less node density than the two random deployments strategies in order to achieve the same level of coverage degree.

In ([11]) authors present a performance study for congestion control between three different algorithms under different node placements. Algorithms that employ three different techniques for congestion mitigation in WSNs. "Traffic control", "resource control" and multipath routing. Simulation results show that the performance of "resource control" algorithms is affected by different node placements.

In ([12]) authors study the energy utilization performance of HTAP algorithm([10]) under specific node placements, in correlation with Directed Diffusion ([9]) algorithm. Simulations results show that the performance of HTAP, a "resource control" algorithm, is improved when nodes are densely deployed near hotspots.


3. Congestion control in WSNs

Congestion in WSNs occurs when the offered load is temporarily higher than the load which node(s) resources can process in a certain amount of time.

Congestion in WSNs can be categorized in two types. The first type of congestion happens in the medium. In this type, two or more nodes attempt to transmit simultaneously and as a result collisions of packets occur in the medium. This type of congestion is normally faced through enhancements in the MAC layer (e.g phase shifting that appeared in ([17]).

The other type of congestion happens when the queue or the buffer of a node used to hold packets to be transmitted, overflows. In such case packets drops happen, which is a highly undesirable situation in low powered WSNs. Solutions for this type of congestion lie in upper layers, like network or transport layer.

Generally, congestion in WSNs is mitigated by three categories of algorithms. "Traffic Control", "resource control" and "reliable data transport". "Traffic control" algorithms, affect the data rate of source nodes in order to reduce the traffic in the network when congestion occurs. Algorithms that employ this method, attempt, normally usually backpressure messages, to inform sources to reduce their data rate, in order to absorb the already high load and avoid packet drops.

On the other hand, "resource control" algorithms employ a different method in order to mitigate congestion. In this case, these algorithms attempt to take advantage of the already dense placement of WSNs, as well as the plethora of nodes that are in sleep state, by creating alternative or multiple paths to the sinks, in order to route the excess data. This type of algorithms do not affect the rate with which sources inject traffic in the network.

Finally, a different category is "reliable data transport" algorithms. This type of algorithms, typically run on the transport layer and focus on reliability. Although they are not "pure" congestion control algorithms, they can be considered as so, since congestion is a condition that affects significantly the reliability of WSNs.

Besides these categories there is another type of algorithms that attempts to create multiple paths in order to ease the transportation of data from source to sink. Although algorithms that fall in this category, cannot be considered as congestion control algorithms, we study them, since multiple paths can assist the network to balance the load and avoid congestion occurrence.

Thus, in this work we study the behavior of a representative algorithm of each category when nodes are placed under different placements. Specifically we employ SenTCP ([8]) as a "traffic control" algorithm, HTAP ([10]) as a "resource control", ESRT [7]) as a "reliable data transport" algorithm as well as "Directed Diffusion" ([9]) as a "multiple path creation" algorithm. Furthermore, we also study "flooding algorithm" which is a generic routing algorithm, for comparison purposes.


4. Node placements analysis

It is clear that node density is only one factor that affects network topology. The actual placement of nodes is also significant, as it is shown in ([13] and [18]). The placement of nodes affects the ability of a network to correctly sense an event while it also affects the number of possible disjoint paths towards the sink(s).

Thus, we claim that the placement of sensor nodes on a monitored field, is a factor that it is possible to affect the overall performance of the network.

Placement of nodes in a network can be divided into three major categories concerning the way that nodes are placed in the field. These are the deterministic node placement, the semi- deterministic node placement and the non- deterministic (stochastic) node placement. In this work we choose to place nodes in four different placements in order to cover all categories. A deterministic placement (Grid), a semi- deterministic (Biased Random) and two non- deterministic (Simple Diffusion and Random).

4.1. Deterministic node placement

In deterministic node placement, nodes are placed on exact, pre- defined points on a grid or in specific parts of the grid. Usually, deterministic or controlled node placement is specified by the type of nodes, the environment in which the nodes will deploy, and the application. Therefore, in applications like Sensor Indoor Surveillance Systems or Building Monitoring, nodes must be placed manually ([13]) (either by hand or by robots). In this work we employ Grid Placement as appears in Fig. . In this placement nodes are placed strictly on the lines of a grid.

Figure 1.

Grid Placement

4.2. Semi- deterministic node placement

Semi- deterministic placement is the placement, where, although individual nodes are placed in a non- deterministic way on the grid (e.g random) the areas where nodes are going to be spread are deterministic. This means that in a microscopic way the placement of nodes is non- deterministic while in a macroscopic way the placement is deterministic. In this paper we employ biased- random placement, where nodes are placed in two specific areas (near source and near sink). Note that the actual node placement is performed in random way in these areas (Fig. )

Figure 2.

Biased Random Placement

4.3. Non- deterministic node placement

Deterministic placement is not so realistic when many sensor nodes are placed in a large area. In such a situation, stochastic placement is needed. In this paper we employ two stochastic placements. Simple Diffusion and Random placement

Simple Diffusion: This node placement emulates the distribution of nodes when they are scattered from air e.g from airplane (Fig. ). Simple diffusion is analytically explained in ([15]).

Figure 3.

Simple Diffusion Placement

Random Placement: This is a commonly used topology and sensor nodes are placed so that their density is uniform. (Fig. )

Figure 4.

Random Placement


5. Congestion control algorithms

In different studies ([17], [19]) it is observed that the number of nodes with occupied queues grows, if congestion gets worse.

Several transport control schemes and algorithms have been proposed in the literature ([7], [8], [10], [17], [19], [20], [21], [22], [23], [24], [25]). Their objectives and approach differs. The vast majority of them ([7], [8] and [17] to [22]) react to congestion with rate limiting techniques ("traffic control" algorithms). Others deal with the problem by increasing the resources ([10], [26], [27]) ("resource control" algorithms). Some focus more on reliability issues instead of congestion ([7], [24], [25]) ("reliable data transport" algorithms). In our evaluation we consider one algorithm from each major category: ESRT ([7]) which is "traffic control" algorithm focusing on reliability, SenTCP ([8]) which is a "traffic control" algorithm focusing on congestion, and HTAP ([10]) which is "resource control" algorithm. We also employ Directed Diffusion ([9]) algorithm, an algorithm not explicitly designed for congestion control but it can be considered as so, since it employs a combination of "traffic control" and "resource control" techniques in order to provide multiple disjoint paths to the sink. Finally we also evaluate the performance of a generic routing algorithm, the "plain flooding".

Short description of employed algorithms follows.

5.1. Sen- TCP (Sensor Based TCP)

SenTCP is an open-loop hop-by-hop congestion control protocol with two special features:

  1. It jointly uses average local packet service time and average local packet inter-arrival time in order to estimate current local congestion degree in each intermediate sensor node. The use of packet arrival time and service time, not only precisely calculates congestion degree, but effectively helps to differentiate the reason of packet loss occurrence in wireless environments, since arrival time (or service time) may become small (or large) if congestion occurs.

  2. It uses hop-by-hop congestion control. In SenTCP, each intermediate sensor node will issue feedback signal backwards and hop-by-hop. The feedback signal, which carries local congestion degree and the buffer occupancy ratio, is used for the neighboring sensor nodes to adjust their sending rate in the transport layer. The use of hop-by-hop feedback control can remove congestion quickly and reduce packet dropping, which in turn conserves energy.

5.2. ESRT (Event to Sink Reliable transport)

ESRT aims at providing reliability from sensors to sink while supporting congestion control simultaneously. It is an end-to-end algorithm trying to guarantee a desired reliability through regulation of sensors reporting frequency. It provides reliability for applications and not for each single packet. The sink uses congestion feedback from sensor nodes to broadcast a notification to adjust the reporting rate with two goals: i) to receive a sufficient number of nodes from the sink, and ii) to receive only as many packets as necessary in order to avoid congestion and save energy. ESRT runs on the sink, with minimal functionality required at resource constrained sensor nodes. ESRT protocol operation is determined by the current network state, based on the reliability achieved and congestion condition in the network. Firstly, it needs to periodically compute the factual reliability r according to successfully received packets in a time interval. Secondly, ESRT deduces the required sensor report frequency f from r. Finally, ESRT communicates f to all sensors through an assumed channel with high power. ESRT identifies 5 characteristic regions:

  1. No Congestion, Low reliability

  2. No Congestion, High reliability

  3. Congestion, High Reliability

  4. Congestion, Low Reliability

  5. Optimal Operating Region (OOR) which essentially translates to No Congestion, Medium-High Reliability

The target is to identify network's current state and bring it in OOR (Optimal Operating Region). If the event-to-sink reliability is lower than the required, ESRT adjusts the reporting frequency of source nodes aggressively in order to reach the target reliability level as soon as possible. If the reliability is higher than required, then ESRT reduces the reporting frequency conservatively in order to conserve energy while still maintaining reliability. This self-configuring nature of ESRT makes it robust to random, dynamic topology of WSNs. An additional benefit resulted from ESRT is energy-conservation since it can control the sensor reporting frequency. ESRT presents some disadvantages:

  1. ESRT regulates report frequency of all sensors using the same value. It may be more reasonable to use different values, since each sensor node may have different contribution to congestion.

  2. It assumes and uses a channel (one-hop) with high power that will influence the on-going data transmission.

  3. It mainly considers reliability and energy-conservation. Feedback latency dependents on the network's size and may not scale in very large sensor networks.

5.3. Directed diffusion

Directed Diffusion is a data centric protocol because all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths (small delay) by caching and processing data in-network (e.g., data aggregation). Directed diffusion consists of four (4) basic elements:

  1. interests

  2. data messages

  3. gradients

  4. reinforcements

An interest message is a query from a sink node to the network, which indicates application demands. It carries a description of a sensing task that is supported by a sensor network. Data in sensor networks is the collected or processed information of an event (e.g. physical phenomenon), it is named (addressed) using attribute-value pairs, while a sensing task is diffused throughout the sensor network as an interest for named data. This dissemination sets up gradients within the network designed to "draw" events (i.e., data matching the interest). A gradient is direction state, created in each node that receives an interest. This direction is set toward the neighboring node from which the interest was received. Events start flowing towards the sinks of interests along multiple gradient paths. To improve performance and reliability, the empirically "good paths" (e.g small delay) are reinforced by the sink and their data rate increases. On the other hand unreliable paths (e.g high delay) are negatively reinforced and pruned off.

5.4. HTAP (Hierarchical Tree Alternative Path)

HTAP is scalable and distributed framework for minimizing congestion and assuring reliable data transmissions in event based WSNs. As such it does not employ rate limiting actions, but tries to maintain a high level of packets data rate while minimizing packet losses. It is based on the creation of alternative paths from the source to sink ("resource control"), using the plethora of network's unused nodes, in order to safely transmit the observed data. The creation of alternative paths involves several nodes which are not in the initial shortest path from the source to the sink. The use of these nodes leads to a balanced energy consumption, avoiding the creation of "holes" in the network and prolonging network lifetime. The HTAP algorithm consists of four major parts.

  1. Flooding with level discovery functionality: Through this procedure, each node discovers its neighbor nodes and updates its neighbor table. In addition, sensor nodes are placed in levels from the source to the sink.

  2. Alternative Path Creation Algorithm: In order to avoid congestion, each candidate congested receiver sends a backpressure packet to the sender. Thus, the sender stops the transmission of packets to the candidate congested receiver and searches in its neighbor table to find the least congested receiver, in order to continue the transmission of data. The dynamic change of the receivers, leads to the creation of new routes from the source to the sink.

  3. The Hierarchical Tree Algorithm: A hierarchical tree is created, beginning at the source node. Connection is established between each transmitter and receiver using a 2-way handshake. Through this packet exchange, the congestion state of each receiver is communicated to the transmitter.

  4. Handling of Powerless (Dead Nodes): Special care is taken in HTAP algorithm concerning the nodes that their power is getting exhausted. Thus, when a node is going to exhaust its power, it is immediately extracted from the network and the tables of its neighbor nodes are updated.


6. Performance evaluation

To evaluate the selected algorithms under the proposed topologies, a series of simulations using ns-2 [28] simulator, has been conducted.

6.1. Simulation environment

In all scenarios we choose to deploy nodes within a square area of size 1000m x 1000m. The results presented are the average of 20 runs for each measurement point. In each set of runs, the parameters of Table 1 were kept stable while increasing the number of nodes in the topology to make a dense network with strong connectivity.

X distance (m) 1000
Y distance (m) 1000
Transmit Power (mW) 600
Receive Power (mW) 600
Sensitivity Threshold (dBm) -81
Path Loss Coefficient 3.5
Node CPU (MHz) 4
Radio Freq. (MHz) 433
Data packet 128 bytes
Control Packet 50 bytes
Initial Node Energy 1 Joule

Table 1.

Simulation Parameters

The evaluation of node placements has been performed by studying four basic QoS parameters. These are: Average Packet Loss, Mean Packet's Delivery Delay, Average Data Rate, as well as the Percentage of Network's Remaining Energy after the point where the network, due to routing "holes" is not able to forward a single packets from source to sink.

6.2. SenTCP evaluation

"Traffic control" is a method used in different algorithms to alleviate congestion in WSNs. SenTCP is one of these algorithms. In Fig. a we record the average data rate in all four examined topologies under SenTCP algorithm.

Initially, when 500 packets/s are injected in the overloaded network, the network experiences a heavy load situation and data rate falls rapidly in order to control the situation. SenTCP then slowly increases the rate until the occurrence of a new packet drop. It is clear that in all four topologies the network exhibits similar attitude and performance. This indicates that this parameter is slightly affected by nodes' placement. This is true, taking into account that SenTCP employs average local packet inter-arrival and packet service time, to detect congestion and "traffic contol" method to mitigate it.

Next we study packet drops. Packet drops is one of the most significant events in terms of performance control and their occurrence indicate a problem in the network. In Fig. b we record Average Packet Drops vs Simulation Time. According to this figure, the attitude of SenTCP algorithm is not affected by different placements. This result is an indication that "resource control" algorithms are not affected by different placements concerning their congestion mitigation ability.

(a) SenTCP:Average Data Rate (packets/s)(b) SenTCP:Average Packet Drops

Figure 5.

SenTCP:Average Data Rate (packets/s) and Average Packet Drops

Also a significant parameter concerning performance control, is the minimization or reduction of delays in the network. In Fig. a we present the mean time for the transmission of packets from source to sink. It is obvious that as the hop number increases, mean time increases too, since hop count is bigger. Considering that, algorithms like SenTCP use the shortest path to transmit their data, it is expected that the placement which is able to provide the shortest path will exhibit the best performance. This happens in Simple Diffusion placement followed by Biased- Random.

The last parameter that we investigate is the percentage of network's remaining energy at the moment where the network is not able to transmit a single packet from source to sink (network stalls). This metric is an indication of whether the network has managed to uniformly utilize its resources, avoiding the creation of network connectivity "holes" (Fig. b).

(a) SenTCP:Mean Packet's Delivery Delay(b) SenTCP:Percentage of Network's Remaining Energy

Figure 6.

SenTCP:Mean Packet's Delivery Delay and Percentage of Network's Remaining Energy

As it is presented in this graph, the network utilizes most of its energy in Simple Diffusion placement while it consumes the least energy in Grid placement. This proves that in Simple Diffusion placement where the nodes are scattered around the sink, the network is able to utilize more uniformly its resources by finding more available paths from source to sink compared to Grid Placement.

6.3. ESRT evaluation

ESRT is an algorithm that focuses on reliability. It is an end-to-end algorithm that runs on the sink and in case of congestion regulates report frequency (data rate) of all sensors using the same value. Fig. a presents the average data rate.

Since ESRT is an algorithm that throttles data rate in order to mitigate congestion, it is expected that average data rate is slightly affected by node placements. The same happens with packet drops (Fig. b).

(a) ESRT: Average Data Rate (packets/s)(b) ESRT:Average Packet Drops

Figure 7.

ESRT: Average Data Rate (packets/s) and Average Packet Drops

On the other hand mean packet's delivery delay" is a parameter that its attitude could be related with nodes placement. Efficient nodes placement can reduce the mean time for the transmission of packets. As it is presented in Fig. a, Simple Diffusion placement and Biased- Random placement (as with SenTCP) are the placements that provide the shortest paths from source to sink and normally present the least delay. Contrary, Grid Placement is a placement that provides longer paths and this is the reason that the delay in this placement is the biggest.

Concerning the percentage of network's remaining energy (Fig.b) we notice that ESRT presents the same attitude as with SenTCP. ESRT when runs on Simple Diffusion and Biased- Random placements presents better performance in comparison with the other two placements. The reason is the same as with SenTCP. These placements provide a bigger number of disjoint paths from source to sink, that, when the nodes that form the initial paths are totally power exhausted, the network is still able to find other paths to forward data to sink.

(a) ESRT:Mean Packet's Delivery Delay(b) ESRT:Percentage of Network's Remaining Energy

Figure 8.

ESRT:Mean Packet's Delivery Delay and Percentage of Network's Remaining Energy

6.4. Directed Diffusion evaluation

Directed Diffusion is an algorithm that mitigates congestion in an indirect way. Initially, it sends an upstream data message to multiple nodes, forming multiple paths and then, with reinforcement and negative reinforcement attempts to reduce the number of paths, to a small number, based on their empirically observed performance. Through this reduction of paths, it controls the data rate of the paths and consequently the network's data rate.

Concerning the average data rate, Fig. a shows that it is affected by the topology. The Biased-Random placement scheme, exhibits the best performance followed by Simple Diffusion and Random Placement. The worst performance is exhibited by Grid Placement. The reason is that in Biased Random Placement, in a higher grade and Simple Diffusion in a lower, there is a high concentration of nodes one hop away from the sink. This leads to the creation of multiple disjoint "good" paths, which can be reinforced by the algorithm, to constantly maintain high data rates. On the other hand, in random placement as well as in grid placement, the nodes around the sink are limited. This leads to few high performance paths and the data rate is kept low.

Packet drops lead to higher latency paths which are not desirable especially in WSNs. Directed Diffusion uses negative reinforcement to prune off higher latency paths.

In Fig.b we record packet drops in all four topologies. It is clear that Simple Diffusion placement, due to the plethora of paths that constantly reinforces, presents null packet drops (after the initial injection of data packets in the network). On the other hand on the other topologies there are some packet drops, but negative reinforcement handles them quickly and efficiently.

(a) Directed Diffusion: Average Data Rate (packets/s)(b) Directed Diffusion:Average Packet Drops

Figure 9.

Directed Diffusion:Average Data Rate (packets/s) and Average Packet Drops

Due to the nature of Directed Diffusion there is not much deviation between the four topologies, concerning mean packet's delivery delay. The reason is the reinforcement of high performance paths and negative reinforcement of low performance paths, which allows to the network to prune off high latency paths. In spite of this, Simple Diffusion followed by Biased- Random placement exhibits the best performance, in comparison with the other placements (Fig.a), since it achieves nearly null number of packet drops (after the first injection of data packets in the network).

(a) Directed Diffusion:Mean Packet's Delivery Delay(b) Directed Diffusion:Percentage of Network's Remaining Energy

Figure 10.

Directed Diffusion:Mean Packet's Delivery Delay and Percentage of Network's Remaining Energy

Directed diffusion presents much better performance compared to ESRT and SenTCP concerning the percentage of network's remaining energy. Comparing the performance of Directed Diffusion in different placements (Fig.b) we record again, that when algorithm runs on placements like Simple Diffusion and Biased- Random, which are capable to provide many paths from source to sink, manages to utilize the network's resources uniformly. Good performance is also presented with random placement, since Directed Diffusion finds multiple paths for forwarding the data from source to sink. On the other hand, placement like Grid, are more vulnerable to the creation of network holes, due to the limited number of nodes near sources and sinks.

6.5. HTAP evaluation

By its nature, HTAP algorithm does not control the data rate of the sources, since it is an algorithm that mitigates congestion through the employment of sleep nodes ("resource control"). As it is expected, the network's data rate is kept stable in all simulation moments and for all topology schemes (Fig.a).

Fig.b presents HTAP's average packets drops. We observe that Biased- Random Placement exhibits the fewer packets drops compared to the other placements. The reason lies on the big number of nodes around sources and sinks. In this algorithm, in which the data rate is not reduced, the existence of many nodes one hop away from source and one hop away from sink is very important. Otherwise, if the nodes around sources and sinks are limited, the network will experience "hot-spot" congestion, at these nodes. This is what is happening in Random and Grid topology. Grid and Random placements face this situation very soon, since the number of nodes around the sources and sinks is limited, while Simple Diffusion faces this situation later due to the larger number of nodes (compared to Random and Grid topology) around the sink.

(a) HTAP: Average Data Rate (packets/s)(b) HTAP:Average Packet Drops

Figure 11.

HTAP:Average Data Rate (packets/s) and Average Packet Drops

In Fig.a we observe that there is a deviation in mean packet's delivery delay between the four topologies, as the node density increases. Biased- Random and Simple Diffusion placements, seem to cope better with the increment of the number of nodes, as this increment creates more data paths. The reason in this case, as well, is the number of nodes around the sink, nodes that can directly forward the data to sink. On the other hand, as fewer nodes are around sink, latency increases due to the "hot spot" that appears near sink.

Concerning the percentage of network's remaining energy (Fig. b), we notice that HTAP exhibits the best performance compared to the other algorithms. The reason is the creation of alternative paths, that employs almost all nodes in the procedure of packets forwarding from source to sink. Comparing the performance of HTAP in the four placements we notice that beside Grid Placement, on the other three placements, HTAP algorithm exhibits very good performance and utilizes more than 90% of network resources. This is a strong indication that "resource control" algorithms can significantly increase the lifetime of a heavy loaded network.

(a) HTAP:Mean Packet's Delivery Delay(b) HTAP:Percentage of Network's Remaining Energy

Figure 12.

HTAP:Mean Packet's Delivery Delay and Percentage of Network's Remaining Energy

6.6. Flooding evaluation

Flooding is generic routing algorithm. When flooding applies, each node forwards every message to every node that is in its radio range. Since it does not implement any "traffic control" functionality in case of congestion, then the sources data rate remains the same (Fig. a).

Fig. b presents average packet drops when flooding algorithm applies. As it is expected packets drops increase while time evolves. The reason lies on the functionality of flooding algorithm. That is the fact, that fills network with multiple copies of the same packet. Comparing just the placements, we notice that the placements that present the worst performance in the previous cases, when flooding applies present the best. Grid and Random are the placements with the fewer nodes around source. Counting that flooding algorithm, forwards every message to every node in its radio range, it is normal that the placements with the fewer paths, limit the number of packets in the network and thus the fewer drops appear.

(a) Flooding: Average Data Rate (packets/s)(b) Flooding:Average Packet Drops

Figure 13.

Flooding:Average Data Rate (packets/s) and Average Packet Drops

(a) Flooding:Mean Packet's Delivery Delay(b) Flooding:Percentage of Network's Remaining Energy

Figure 14.

Flooding:Mean Packet's Delivery Delay and Percentage of Network's Remaining Energy

The same attitude is depicted with mean packet's delivery delay (Fig. a ). Again placements that create fewer paths are able to forward the data sooner.

Finally we check the percentage of network's remaining energy when the network stalls (Fig. b). In this case we also notice that placements with fewer nodes around source (Grid and Random placements) present better performance compared to the other placements. The reason lies on the operation of Flooding algorithm, (each node transmits each packets to all of its children). This leads to a bigger amount of transmissions from the nodes that have many children around source (this happen in Biased Random and Simple Diffusion placement) and soon these nodes are getting power exhausted. This leads to the creation of a "hole" around source and network "stalls".


7. Conclusions

In this paper we evaluated the performance of specific routing and congestion control algorithms when nodes are deployed under different placements. The algorithms we examined are ESRT ([7]), Sen- TCP ([8]), Directed Diffusion ([9]), HTAP ([10]) and Flooding, in Simple Diffusion, Random, Grid and Biased- Random Placements. Each algorithm represents a special category of congestion control and routing algorithm. ESRT is "reliable data transport" algorithm, SenTCP is a congestion control algorithm that mitigates congestion using "traffic control" method, Directed Diffusion discovers and maintains multiple high performance paths for transmitting packets from source to sink while HTAP is a congestion control algorithm that employs "resource control" method. Finally, flooding is a generic routing algorithm, that its functionality lies on the fact that each node tries to forward every message to every one of its neighbor nodes.

Simulation results show, that algorithms that employ multiple and alternative paths, either by default (Directed Diffusion) or as a response to a congestion situation (HTAP), for the transmission of data from source to sink are significantly favored by denser placements of nodes around source and sink since they can create many paths. This leads to fewer packet drops, while they extend significantly network's lifetime. On the other hand algorithms that always employ the shortest path for the transmission of packets from source are not affected by different node placements and in case of continuous heavy load they present shortest network's lifetime.


8. Future work

Node placement is proven to be an effective way, for optimizing the performance in WSNs concerning "resource", congestion control algorithms. A future work on this subject would be the application of these placements on a real WSN environment and study the performance on a real network. Moreover, it would be worth studying what placements can assist "traffic control" algorithms to increase their performance. Initial results show that placements that create short paths from sources to sinks can assist in this direction. Finally, other parameters like fault tolerance, fault recovery, etc., are possible to be affected by different node placements. Examination of these issues constitutes part of our future work on the subject.


9. Acknowledgment

This work has been partly conducted under the European Union Project GINSENG funded under the FP7 Program (FP7/2007-2013) grant agreement no 224282.


  1. 1. Alberto Cerpa, Jeremy Elson, Michael Hamilton, Jerry Zhao, Deborah Estrin, and Lewis Girod. Habitat monitoring: Application driver for wireless communications technology. In SIGCOMM LA '01: Workshop on Data communication in Latin America and the Caribbean, pages 20–41, New York, NY, USA, 2001. ACM.
  2. 2. E. Biagioni and K. Bridges. The applications of remote sensor technology to assist the recovery of rare and endangered species. International Journal of High Performance Computing Applications, Special Issue on Distributed Sensor Networks, April 2003.
  3. 3. Loren Schwiebert, Sandeep K. S. Gupta, and Jennifer Weinmann. Research challenges in wireless networks of biomedical sensors. In MobiCom '01: Proceedings of the 7th annual international conference on Mobile computing and networking, pages 151–165, New York, NY, USA, 2001. ACM Press.
  4. 4. H. T. Kung and D. Vlah. Efficient location tracking using sensor networks. In IEEE Wireless Communications and Networking Conference (WCNC), pages 1954–1962, March 2003.
  5. 5. R.R. Brooks, P. Ramanathan, and A. M. Sayeed. Distributed target classification and tracking in sensor networks. Proceedings of the IEEE, 91(8):1163–1171, 2003.
  6. 6. B.C. Srean, J.S. Silva, L. Wolf, R. Eiras, T. Voigt, U. Roedig, V. Vassiliou, and G. Hackenbroich. Performance control in wireless sensor networks: the ginseng project - [global communications news letter]. Communications Magazine, IEEE, 47(8):1 –4, august 2009.
  7. 7. Y. Sankarasubramaniam, O. Akan, and I. Akyildiz. ESRT: Event-to-Sink Reliable Transport in Wireless Sensor Networks. In MobiHoc '03: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pages 177–188, New York, NY, USA, 2003. ACM.
  8. 8. C. Wang, K. Sohraby, and B. Li. SenTCP: A Hop-by-Hop Congestion Control Protocol for Wireless Sensor Networks. IEEE INFOCOM (Poster Paper), March 2005.
  9. 9. Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, and Fabio Silva. Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Transactions on Networking, 11(1):2–16, 2003.
  10. 10. Charalambos Sergiou, Vasos Vassiliou, and Andreas Pitsillides. Reliable Data Transmission in Event-Based Sensor Networks During Overload Situation. In WICON '07: Proceedings of the 3rd International Conference on Wireless Internet, pages 1–8, Austin, Texas, October 2007.
  11. 11. V. Vassiliou and C. Sergiou. Performance Study of Node Placement for Congestion Control in Wireless Sensor Networks. In New Technologies, Mobility and Security (NTMS), 2009 3rd International Conference on, pages 1 –8, dec. 2009.
  12. 12. Charalambos Sergiou and Vasos Vassiliou. Energy utilization of HTAP under specific node placements in Wireless Sensor Networks. In Wireless Conference (EW), 2010 European, pages 482 –487, 12-15 2010.
  13. 13. Mohamed Younis and Kemal Akkaya. Strategies and Techniques for Node Placement in Wireless Sensor Networks: A Survey. Ad Hoc Networks, 6(4):621–655, 2008.
  14. 14. Stavros Toumpis and Leandros Tassiulas. Optimal Deployment of Large Wireless Sensor Networks. IEEE Transactions on Information Theory, 52(7):2935–2953, 2006.
  15. 15. Mika Ishizuka and Masaki Aida. Performance Study of Node Placement in Sensor Networks. ICDCSW '04: Proceedings of the 24th International Conference on Distributed Computing Systems Workshopsd, pages 598–603, March 2004.
  16. 16. H. Zhang and J. C. Hou. Is deterministic deployment worse than random deployment for wireless sensor networks? In INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pages 1–13, April 2006.
  17. 17. A. Woo and D. E. Culler. A Transmission Control Scheme for Media Access in Sensor Networks. In Proceedings of the 7th annual International Conference on Mobile Computing and Networking (MobiCom'01), pages 221–235, New York, NY, USA, 2001. ACM Press.
  18. 18. Sameer Tilak, Nael B. Abu-Ghazaleh, and Wendi Heinzelman. Infrastructure tradeoffs for sensor networks. In WSNA '02: Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pages 49–58, New York, NY, USA, 2002. ACM.
  19. 19. Chenyang Lu, Brian M. Blum, Tarek F. Abdelzaher, John A. Stankovic, and Tian He. RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks. Technical report, Charlottesville, VA, USA, 2002.
  20. 20. Cheng Tien Ee and Ruzena Bajcsy. Congestion Control and Fairness for Many-to-One Routing in Sensor Networks. In SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 148–161, New York, NY, USA, 2004. ACM.
  21. 21. Bret Hull, Kyle Jamieson, and Hari Balakrishnan. Mitigating Congestion in Wireless Sensor Networks. In SenSys '04: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, pages 134–147, New York, NY, USA, 2004. ACM.
  22. 22. Chieh-Yih Wan, Shane B. Eisenman, and Andrew T. Campbell. CODA: Congestion Detection and Avoidance in Sensor Networks. In SenSys '03: Proceedings of the 1st international Conference on Embedded Networked Sensor Systems, pages 266–279, New York, NY, USA, 2003. ACM Press.
  23. 23. Karthikeyan Sundaresan, Vaidyanathan Anantharaman, Hung-Yun Hsieh, and Raghupathy Sivakumar. ATP: A Reliable Transport Protocol for Ad Hoc Networks. IEEE Transactions on Mobile Computing, 4:588–603, 2005.
  24. 24. Fred Stann and John Heidemann. RMST: Reliable Data Transport in Sensor Networks. In Proceedings of the First International Workshop on Sensor Net Protocols and Applications, pages 102–112, Anchorage, Alaska, USA, April 2003. IEEE.
  25. 25. Chieh-Yih Wan, Andrew T. Campbell, and Lakshman Krishnamurthy. P.S.F.Q: A Reliable Transport Protocol for Wireless Sensor Networks. In WSNA '02: Proceedings of the 1st ACM international workshop on Wireless Sensor Networks and Applications, pages 1–11, New York, NY, USA, 2002. ACM Press.
  26. 26. Jaewon Kang, Yanyong Zhang, and Badri Nath. TARA: Topology-Aware Resource Adaptation to Alleviate Congestion in Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, 18(7):919–931, 2007.
  27. 27. C. Sergiou and V. Vassiliou. DAlPaS: A Performance Aware Congestion Control Algorithm in Wireless Sensor Networks. In Telecommunications (ICT), 2011 18th International Conference on, pages 167 –173, may 2011.
  28. 28. The Network Simulator ns-2 (v2.1b8a)., October 2001.

Written By

Charalambos Sergiou and Vasos Vassiliou

Submitted: 12 November 2011 Published: 18 July 2012