BDCC: Backpressure routing and dynamic prioritization for congestion control in WMSNs

Published Online April 2014 in MECS

Congestion in a network [1] is a situation in which the demands for resource are more than available resources in the network and results lower performance and more delay. Developing protocols, algorithms and structures to maximize network lifetime cause a serious problem as well as satisfying the QoS requirements. Basically, traffic flows from some sensor nodes to the main node. Data are generated and sent to main node typically in the WMSNs. However if an important event is discovered or recognized, a traffic of data series can be generated, and for the packets with more important data, the network requires to attempt more effectively to deliver them. For example, in an event detection system, data are sent to the main node in specified intervals. However, if an important event happens in the system and the sensor node senses this event, it should send a message to the main node. This message can be a combination of packets including information like date and time. Although WMSNs is a promising technology and can be used in different fields, there are still some problems that should be solved in order to achieve an advanced technology [1], [2]. One of the main problems is energy restriction caused by cheap sensor nodes, which use batteries as main energy source. Because these barriers cannot be eliminated in the near future, optimized designing of WMSNs for consuming energy becomes important. In WMSNs, it is believed that communication dominates energy consumption [2], [3]. Data sensing and calculating energy costs are less than transmitting it. Cost of transmitting 1kb to 100 meters distance equals to the cost of performing 3 million instructions using a generalpurpose processor. So, reducing energy consumption by using communication is the key to relief from energy shortage in WMSNs. At the moment, information about communications in WMSNs especially in the fields of traffic and communication patterns is relative and ambiguous. Surely, any information about traffic properties and communication patterns can help to understand energy consumption and its distribution in WMSNs. So, traffic properties and communication patterns would be a good point to start finding an energy saving WMSNs. Some new solutions for optimized designing of WMSNs in order to efficient energy consuming are proposed in the following [3], [8].

Previous efforts in the field of sensing networks are mainly concerned with two qualitative differences, which include congestion reduction so, the following problems are caused as a result of congestion reduction. In a sensing network, if the sensors are provided to sense environmental data and send them at certain periods, then if data traffic exceeds network capacity, nodes order and thus network output will determine justice degradation. It is different from congestion control, because finding the sensor nodes with higher justice most influenced the process. In this case, network is most efficient and the output of each node is close to the sent value, when the nodes transmit the information at an optimal rate [3], [6].

Two main operations in transmission layer of WMSNs are delivering reliable data and congestion control. To submit reliable data, this layer reviews and identifies missing data and recovers them. Data reliability is more important when the data is going to be used in critical operations. There are different types of congestion control such as data traffic, route discovery traffic, interface layer feedback and etc. This article is mainly concerned with data traffic and does not pay much attention to other kinds of traffic. It has been proved that if there is no control over the network congestion, bandwidth increase would not help solving congestion problem at all. Especially in the wireless networks, congestion wastes lots of energy and eliminates lots of data packets. So it is necessary to congestion control in order to improve network lifetime in WSNs. By using backpressure routing, connections are minimized; more important data are protected and delivered in the network, by using dynamic prioritization for service differentiation [5], [6].

Many protocols have been set in the transmit layer for this purpose and we will review some of them in the following sections. There is an enormous diversity in the congestion scenarios, which are outside the scope of this article.

This research has been formed as follows; section II includes a summary of related works and describes some of the WMSNs protocols. This Section is related to the issues encountered during designing different types of congestion and congestion control in WMSNs. BDCC is given in section III. Section IV gives us an evaluation of simulation results and the conclusion of the research is included in section VI.

• II.    Related Works

Congestion control is an important issue in transport protocols. Congestion is also a difficult problem in wireless sensor networks. It not only wastes the scarce energy due to a large number of retransmissions and packet drops, but also hampers the event detection reliability. Congestion in WSNs and WMSNs has a direct impact on energy efficiency and application QoS. Two types of congestion could occur in sensor networks [6]. The first type is node-level congestion that is caused by buffer overflow in the node and can result in packet loss, and increased queuing delay. Not only can packet loss degrade reliability and application QoS, but it can also waste the limited node energy and degrade link utilization. In each sensor node, when the packet-arrival rate exceeds the packet service rate, buffer overflow may occur. This is more likely to occur at sensor nodes close to the sink, as they usually carry more combined upstream traffic. The second type is link-level congestion that is related to the wireless channels which are shared by several nodes using protocols, such as CSMA/CD (carrier sense, multiple access with collision detection). In this case, collisions could occur when multiple active sensor nodes try to seize the channel at the same time.

As was shown in [6], CCF is a non-work-conserving algorithm. To explain the non-work-conserving property of CCF, suppose that a root node is connected to two nodes A and B. The non-work-conserving property of CCF implies that the root node will wait until the required number of packets has been received and transmitted from node B before considering packets from node A. This also implies that CCF cannot effectively allocate the remaining capacity, resulting in a low throughput, especially, when some nodes do not have any packet to send. Further, as was shown in [6], CCF has another major problem. The rate adjustment in CCF relies only on packet service time which could lead to low utilization when some sensor nodes do not have enough traffic or there is a significant packet error rate.

Priority based congestion control protocol (PCCP) was proposed in [6]. PCCP is an upstream congestion control protocol for WSNs which measures the congestion degree as the ratio of packet inter-arrival time to the packet service time. Based on the introduced congestion degree and node priority index, PCCP utilizes a cross-layer optimization and imposes a hop-by-hop approach to control congestion. It has also been shown that PCCP achieves efficient congestion control and flexible weighted fairness for both single-path and multipath routing. In wireless sensor networks data are normally generated and sent to the sink periodically. However, a burst of data traffic can also be suddenly generated when an important event is triggered or detected. So, in wireless sensor networks different data packets might have different importance. For packets containing information with higher importance, the network should make more effort in delivering them. This highlights a need for having service differentiation in sensor networks. Service differentiation in wireless sensor networks is a new research area and a few methods have been proposed [6], [7].

Earlier works in the field of sensing networks are mainly concerned with two qualitative differences, which include congestion reduction [2]. So, the following problems are caused as a result of congestion reduction. In a sensing network, if the sensors are provided to sense environmental data, send them at certain periods, then if data traffic exceeds network capacity, nodes order and thus network output will determine justice degradation. It is different from congestion control, because finding the sensor nodes with higher justice has the highest impact on the process. In this case, the nodes transmit the information at an optimal rate, network is most efficient and the output of each node is close to the sent value. Adaptive Roll Control (ARC) indicates packet injecting to traffic flow like straight route traffic. Each node estimates the number of nodes in the neighborhood of Sink and the bandwidth is divided between straight route traffic and local traffic based on their priority. Division bandwidth of each node is an effort to achieve approximate justice. Reduction in the straight traffic transfer also affects upper nodes, which can reduce transmission rate [2], [6].

• A.    Congestion and Congestion Control

Basically, congestion control is allocation of resources. Congestion control adjusts source transmission rate to avoid or reduce congestion. Congestion is an important problem in transmission protocols and network, especially wireless networks, due to lack of energy supplies. Congestion on the networks has a direct effect on energy efficiency and QoS appliance. There are two reasons that cause congestion in WMSNs: Node-level congestion, Link-level congestion [6].

(Illustrated in Figure1) It has direct impact on energy efficiency and QoS.

Fig. 1. Two types of congestions in WMSNs [6].

• B.    Congestion Control Solution

The main solution in congestion control is to predict congestion. But beside that, after congestion appeared, three main tasks should be done: Finding congestion, reporting congestion and adjusting transmission rate.

• III.    Details of the Proposed Scenarios (BDCC)

Network tries to deliver more important packets of data, yet there is not a static value to show importance of any packet of data.

So we use backpressure routing (also written "backpressure routing" or "back pressure routing") algorithm to prioritize packets. In this algorithm, the routes are not selected beforehand, but the next step is chosen dynamically. These decisions are made based on congestion of neighbor nodes. Each node sees its own queue backlog and its neighbor's queue backlog and adjusts its own rate and select routes based on queue backlog of its neighbors [4], [5].

• A.    Choosing the optimal commodity in Backpressure routing:

An example shown in Figure 2, We assume that there are only three types of data in queue.

Real time (Red), Not real time with high priority (Green) and Not real time with low priority (Blue).

These are in correct numbered packets. Focusing on direct link (1, 2) differential queue backlog would be:

Fig. 2. Differential Queue Backlog [5].

^^(O-Qz^tO^i ^^(t) - ^^«n)^ = 2 С/^И-е/6^)^^

So, optimum packet to send on links (1, 2) in the T slot would be not real time with high priority (Green). On the other hand, optimum packet to send on reversed links of (2, 1) in the T slot would be not real time with low priority (Blue). To make it simple, we assume that the topology has only 4 options, shown in Figure 3. The options in Figure 3 are provided in a matrix shown in Figure 4 [5].

Fig. 3. Provided Topology

"0000201      Г 0 0 0 0 0 0 " 0 0 0 0 0 0               0 0 1 0 0 0 _ 0 0 0 0 0 0         _ 0 0 0 0 0 0 0  0  0  0  0  0 ’            0  0  0  0  1  0 0  0  0  0  0  0               0  0  0  0  0  0 0 0 0 0 о о]         [о 0 0 0 0 0 "0000001      ГО 0 0 0 0 0 " 1 0  0  0  0  0                0  0  0  0  0  0 _ 0 0  0 0 0  0         _   0  1  0 0 0  0 0 0 0 0 1  0 '  ^"   0 0 0 0 0 0 0 0  0  0  0  0                0  0  0  1  0  0 0 0 0 0 о о]         [о 0 0 0 0 0

Fig. 4. Matrix for Provided Topology

As we can see, node number 6 cannot send or receive any data based on these possibilities. This may happen, because the node number 6 is out of transmission range at the moment. Total weighted scores for each possibility are:

Choice (a):

Choice (b):                            .

Choice (c):                            .

Choice (d):

Since there are two nodes with total weight of 12, network controller in the backpressure routing can choose any or both of these options (        ) ore choose one of the matrix [5]. Data priority in this paper is based on [6], [7]. That is, for the nodes with same weight, we use dynamic prioritization for service differentiation.

• B.    Dynamic Prioritization for Service Differentiation

If there are two or more data with same condition, we use dynamic prioritization for service differentiation. That is, network should do most efforts to deliver data packets with real time or high priority. Our BDCC method consists of three different traffic levels: Real time traffic level, not real time traffic level with high priority and not real time traffic level with low priority.

Throughput and delay for BDCC is calculated from the equation below:

Throu:HP = > Throu:NP = > Throu:LP Delay:HP< =Delay:NP< =Delay:LP

Each node sees neighbor nodes and their queue backlog. Data is sent to nodes with less crowded buffer queues. If the buffer queues of all nodes are crowded, then data with real time priority are sent based on dynamic prioritization for service differentiation. After that, non-real time data with high priority and non-real time data with low priority are sent. If the buffer of any node is near to congestion threshold and real time data could not enter the queue, non-real time data with lower priority will be eliminated from queue until non-real time data with high priority move to this queue, new entrants data that real time data after real time queuing Placed.

Note that the optimal decisions and good choices backpressure routing is true for dynamic priority algorithms to differentiate service. It means that, if the differential backlog queue does not match with optimal product selection decisions and the backpressure routings, dynamic priority algorithms do not apply to differentiate service for data and path.

• C:    Congestion detection mechanism:

Congestion detection mechanism uses two congestion indexes.

First: Queuing delay is the primary congestion index.

Second: Packet loss is the next congestion index. Congestion control strategies based on packet loss to keep high bandwidth is employed when delay based strategy act inefficiently. Proposed algorithm is applied to the network when these two indexes have been settled.

In general case, proposed algorithm is not applied in normal case since computation is a time consumer manner. Proposed algorithm is applied to the nodes near the base station (which convey more traffic) after the congestion detection mechanism detected the congestion.

• IV.    Simulation Results

We choose NS-2 simulator for researching based on investigation performed on simulator software including (OPNET, OMNET, MATLAB, NS-2, NS-3…) because of its flexibility and performance. Values assigned to the parameters for simulation are table 1.

Table 1. Values of Parameters for simulation

Simulator Routing	NS2 2.29-3 and 2.34 AODV
Simulation	20, 40, 60, 80, 100, 120
duration(Sec)
Simulation area	1000m X 1000m
Number of nodes	200
Transmission range	10 m
Movement	Chain topology
MAC Layer	CCF, PCCP
Queue Size	200
Packet rate	4 packets/sec
Traffic type	CBR (UDP)
Data payload	512 bytes/packet

As it is shown in diagrams, we compared our BDCC with CCF and PCCP protocols. Five and six Figures approve and display average network delay and packet loss. This is the reason that the BDCC shows better performance .

Fig. 5. Average network delay

^CCF ^PCCP ^PROPOSED N^

Ш к и <

(Л in О

Fig. 6. The Lost Packets

As it has always been said, congestion control is directly related to energy consumption, figure seven expresses this fact that BDCC optimize the energy consumption and have a longer network lifetime in comparison with CCF and PCCP.

Fig. 7. Power Consumption Network

Figure eight and nine illustrated that, BDCC is better in terms of average throughput and packet delivery ratio.

^^CCF ^►PCCP ^PROPOSED *^

Fig. 8. Average throughput

Fig. 9. Packet delivery ratio

Figure ten shows normalized routing load. Average efficiency of the BDCC is compared with listed protocols.

• V.    Conclusion

New applications made possible by rapid improvements and miniaturization in hardware has motivated recent developments in wireless multimedia sensor networks (WMSNs). To provide the required quality of service for multimedia applications in WMSNs, congestion control is necessary. Each congestion control protocol should be able to detect congestion in advance, and allocate available rates to the sensor nodes accordingly.

For some applications, there is a need to send real time traffic toward the sink node with low latency and high reliability so that immediate remedial and defensive actions can be taken, as appropriate. Further, when an important event occurs in the system, the sensor node that detected the event should send some alarm message to the sink. Usually this kind of high priority traffic is bursty. This means that high priority traffic is generated only for a short period of time while low priority traffic usually exists in the network and produce thousands of packets generated periodically. For such environments, service differentiation in wireless multimedia sensor networks becomes an important problem. To provide service differentiation in WMSNs, it is necessary to consider a different priority for each traffic source.

In this paper we presented a new method for congestion control by using backpressure routings and service differentiation in WMSNs. We used backpressure routing in this article. This algorithm does not precalculate routes and next step is selected dynamically. Each node sees its own queue backlog and its neighbor's queue backlog and adjusts its own rate and selects routes based on queue backlog of its neighbors. We also used dynamic prioritization for service differentiation. If there are two or more data with same condition in backpressure routing, we use dynamic prioritization for service differentiation. That is, network should do most efforts to deliver data packets with instant or high priority.