Keywords

1 Introduction

Routing protocol design is an important research area in wireless sensor networks, reliable, low-cost, and easy to maintain are design goals of WSN routing protocol, Single path routing algorithms in WSN focus on picking up an energy efficiency path from interconnect sensor nodes network, e.g., DD [1, 2], Minimum Cost Forwarding [3, 4]. They make sure data is transmitted on optimized path and prolong the lifetime of the network. Besides energy efficiency, multipath routing take advantage of interconnect nodes network to enhance data throughput and packet delivery ratio. Hop-based routing protocol has been receiving extensive attention for its simple and effective design ideas.

In WSN, both suddenly burst large amount of information and frequent event reporting will rapidly create shortage of resource (buffer space, energy) which leads to congestion and consequently packet drops. Congestion often happen in the middle or near the sink node of the network, it causes the reduction of node throughput and packet delivery ratio. It also increases time delay and energy wastage. Congestion control in WSN is particularly difficult as data is periodically collected in response to detected event. In Wireless Multimedia Sensor Networks (WMSN) [5, 6], video sensors are used to enhance the capability of event description [7]. Video sensors can generate image and video streaming data, which with heavy load require higher transmitting capability (bandwidth). Since high transmit rate is required for multimedia packages, congestion in WMSN is more prone to happen. So, congestion control is of prime importance in WMSN.

The problem of congestion control has been addressed in many works, e.g., CODA, ESRT. They analyze how to detect and control congestion but mainly under transport layer. For addressing multimedia packets transmitting congestion problem and assure reliably, we believe cross-layer scheme which considering under the whole framework will benefit in solving this problem. In this work, we not only consider proposing a routing algorithm underneath in WMSN but also the congestion problem following this algorithm. For this target, we proposed a Minimum Hop Disjoint Multipath routing algorithm with Time Slice load balancing congestion control scheme (MHDMwTS) to ensure reliability in WMSN.

The concept of minimum hop count (MHC) routing is introduced in papers [8], sink flooding package to whole sensor field to form gradient hop count field. Considering energy, the source transmits data only from bigger hop count number nodes to small number nodes. The strength is that every node in the field can easily find an energy efficient route to sink. But by sending packets to all available neighbors will cause short network lifetime for wasting too much energy in nodes. Also no specified multiple paths to transmit multimedia packets will easily cause congestion at the nodes near sink. In our work, after minimum hop count field formed, most efficient disjoint paths with least time delay will be selected to transmit packets.

Fully disjoint path from source to sink is not easy to form at building up phase of sensor network. Considering resilient and energy, after primary path is constructed, without global topology knowledge, disjoint paths are dynamically constructed. It requires much computation and time in nodes to find the alternate path and the path found could be long. In our proposition, the computation is happened at sink and the alternate path is chosen quickly after primary path constructed. And the length of the paths is all under minimum hop field control. The simplicity and time is of prime importance in our routing algorithm.

In this paper, an improved hop-based routing protocol (REERP) is proposed. Like MHC [2] protocol, REERP divides network work cycle into gradient phase and data transmission phase. In gradient phase, nodes delay in sending gradient packets to avoid redundancy packets and reduce cost of establishing gradient; in data transmission phase, REERP makes parents and siblings as forward selection; a formula (routeScore) makes comprehensive consideration of the forward selection. A trigger update mechanism guarantees a real-time dynamic network topology.

2 Strategies of REERP

REERP also belongs to a hop-based routing protocol in that it utilizes “hop count information” of sensors towards a sink for packet forwarding. The protocol has two phases: Gradient setup phase, Data transmission phase, and also has own routing update mechanism.

2.1 Gradient Setup Phase

  1. Step 1:

    When a sensor (source) is activated, it will send out the path build request package to the neighbors where hop count is smaller than the sink. The neighbors receive the request package and add node number of itself into the package, also add the timestamp of this node, then send out to its smaller hop count neighbors. This package which contain the route node number and transmit from high hop count to low will finally reach to the sink. The first package reaches the sink which with least time delay contains the primary path information. Each sensor node starts Time Out timer when it receives first INIT packet, the timer composes of two fractions, one fraction will be chosen proportional to the measured LQI-value in the incoming INIT packet, the other fraction will be a coefficient μ(1), go to step 3)

  2. Step 2:

    After the first package reach the sink, there still have other packages coming from different routes to the sink. When a new package arrives, extract the route and compare to the primary path. The comparison is simple. If there is joint node, then discard the package. If not, the alternate path is found. Continue to receive package and compare with both primary and alternate path to find the backup path. If after a timeout the backup path is not found, then give up on backup path. At last, paths are found

  3. Step 3:

    Put each INIT packet information into alternative queue, then compare HCself with HCINIT packet plus 1, if HCself > HCINIT packet +1 or HCself is NULL, then to HCself set HCINIT packet +1, otherwise do not update HCself

  4. Step 4:

    If the timer times out, then broadcasts own INIT packet with own information, then go to step 4), otherwise go to step 2);

  5. Step 5:

    Check alternative queue, put the node information whose HCINIT packet = HCself + 1 into parent table, and put the node information whose HCINIT packet = HCself into sibling table, silently drop any other node information

2.2 Data Transmission Phase

One sensor node’s state goes into data transmission phase if the following conditions meet: HCself is not NULL; alternative queue is empty. This can ensure that: current node has own HC; current node’s two tables have been completed in part; current node will not process data packet before the condition above.

The sensor nodes will collect and send data periodically and forward data packet whose relay node ID is they. When choosing relay node, source node considers parent nodes and take priority of sibling nodes; in parent or sibling table, source node chooses only one optimal relay node considering rest energy, communication capacity and history record, which is defined in a formula, routeScore. Relay node needs to reply ack if it forwards data packet successfully.

Source node will choose relay node that has the highest route Score in one table (parent or sibling). rest Energy and LQI are got from INIT or ack packets of related next hop node; success Rate is transmission success rate (0–100), initialized as 100, the rate of related next hop node will be reduced by 1 if one time the source node doesn’t get ack reply. α, β and γ are weighted coefficients. The sum of weights, α, β and γ, is set to 1, and α has highest weight because current rest energy of relay node is the most critical index of evaluating node capacity.

Sensor node selects unique relay node to forward data at one time, which avoids redundancy of data packets; ack mechanism not only offers transmission reliability, but also helps source node update tables timely; rest energy and LQI value represent current capacity of relay node, success Rate represents history forwarding record of relay node, so considering these two aspects, source node can have a more optimal choice.

2.3 Topology Maintenance and Update

Network topology will change with the node energy consumption and other factors, so the initial routing tables can not reflect the current network topology. In REERP, data packet has a new bool field: update and the default value are FALSE. In data transmission phase, sensor node checked HC value of every data packet received, if HC ≥ HCself + 2 or HC ≤ HCself-2, proves that the node receives data packets except parent, sibling and child nodes, which means topology is changed. The paper regards this as trigger update condition, then the node sets update field of next data packet to TRUE, chooses a relay node in tables and broadcasts this data packet, meanwhile clears up two tables. The neighbors reply ack packet if receive this “update” data packet to help the source node rebuilds two tables.

3 Simulations and Results

3.1 Simulation Setting

Omnet ++ 4.1 [9] is the simulation tool to simulate and analyze simulation results. The simulation was implemented with OMNet ++. We considered a square sensor field of size 400 × 400 m2 where 28 static sensor nodes are randomly deployed, channel delay is 100 ms, packet size is 16 bytes, packet loss rate is 5 %, TTL (time to live) is eight, initialized energy capacity is 1,000 units, sending one packet consumes one unit, receiving one packet consumes 0.5 unit, sensor node is regarded as “dead” if energy under 300 units. In radiation layout, 25 nodes are randomly distributed in sensor nodes area, and the horizontal coordinate is frequency to send packets, namely packet rate; this simulation has contribution to analyze the affects of different packet rate in a fixed network. In surrounded layout, the horizontal coordinate is the number of sensor nodes; this simulation has contribution to analyze the affects of different network size.

Simulation factors including:

  • Network lifetime: the simulation duration.

  • Energy per packet: measure the energy expended per delivered data packet.

  • First Node Dead (FND): measure average number of packets delivered to sink when first sensor node is dead.

  • Packet delivery ratio: measure the percentage of data packets generated by the nodes that are successfully routed to sink.

  • Network maintenance cost: measure the proportion of routing packets and data packets generated.

3.2 Simulation Results

Figure 12.1 shows average energy consumption of one data packet in different routing protocols. Figure 12.2a shows that REERP can transfer data more efficiently than other protocols in higher packet rate. Figure 12.2b shows that in fixed packet rate, with growth in the number of nodes, average energy consumption is growing in all protocols, and the result of REERP is similar with that of join-MHC.

Fig. 12.1
figure 1

Energy per packet value at: a different packet rate and b different number of nodes

Full size image
Fig. 12.2
figure 2

Packet delivery ratio value at: a different packet rate and b different number of nodes

Full size image

The simulation results of Fig. 12.3 show that REERP makes sink receive more nonrepetitive data packets from entire network in not only different packet rate but also different network size, which is ensured by parent-sibling design, route Score formula, and ack mechanism.

Fig. 12.3
figure 3

Network maintenance cost at: a different packet rate and b different number of nodes

Full size image

Figure 12.4 shows the cost of building and maintaining network in different packet rate and different network size. Figures 12.4a, b both prove that REERP pays a minimum price to maintain network topology, which is ensured by the delay forwarding in gradient phase and trigger update mechanism in data transmission phase. In Join-MHC, more useless join packets generates in gradient phase, and in data transmission phase sensor nodes also update routing information periodically.

Fig. 12.4
figure 4

a Network lifetime at different packet rate and b FND value at different number of nodes

Full size image

4 Conclusion

This paper summarizes the status of hop-based routing protocols for WSN, and analyses strengths and weaknesses of them, and then designs a new routing strategy, REERP. We have demonstrated through the simulation that our proposition achieves higher data receive rate and longer network life time, which more reliable than normal multipath without congestion control. But under higher package transmit rate from source, both receive rate and network life time will drop fast. And the redundancy is low in our design. These problems affect the reliability of our design and which need further study. The design of a more reliable routing protocol, which apples to large-scale dynamic network, is the next step focus.