# Reliable Multicasting Service for Densely Deployed Military Sensor Networks

Authors: Woongsoo Na; Nhu-Ngoc Dao; Sungrae Cho
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Wireless sensor networks (WSNs) have drawn attention for military applications where a large number of light-weight sensor nodes can detect enemies and intruders in the battlefield and alert a command post (CP) to our forces. In particular, in the military sensor networks, QoS (quality-of-service) is one of the most important requirements to support their mission-critical applications. However, achieving reliable data transmission is not an easy task because sensor nodes are densely deployed and wireless channel is unpredictable due to high mobility. Also, in the multihop deployed sensor networks, redundant data forwarding occurs frequently and it causes interference among the nodes. In this paper, we propose an efficient reliable multicast scheme using pre-ACK frames to provide fully reliable multicasting and decrease unnecessary data forwarding in the military sensor networks. When a receiver node overhears a multicast frame, the pre-ACK is used to announce its reception of the multicast frame to neighboring nodes which then do not need to duplicate the same multicast frame to it. The performance evaluation shows that the proposed scheme provides full reliability (100%) and outperforms the existing schemes in terms of aggregate throughput (612%) and energy consumption (514%) when the number of nodes is 512 with full buffer.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) consist of a large number of small- and light-weight sensor nodes which sense the environment and exchange the gathered information with each other or transfer to the sink nodes (controller or monitoring nodes). The sink nodes process collected information and dispatch respond command to the sensor nodes. Due to the advantages of sensor technology and wireless communications, WSNs have various applications for military, healthcare, intelligent transportation, and disaster preventing systems.In military environment, wireless sensor technology is widely used to manage unauthorized access. Some special applications are deployed such as enemy and intruder detection systems in the battlefield and difficult areas where the human cannot access, alert system for the command post (CP), or control unit of the abnormal activities.Although the military applications enabled by WSNs are very attractive, there are many technical challenges that must be overcome in order to build well-functioning robust systems. The QoS (quality-of-service) requirements of mission-critical applications are very important. For instance, sensor and sink nodes should reliably exchange their information to guarantee decision-making in real time. Since a large number of sensor nodes are densely deployed and the native behavior of wireless communication is unpredictable due to the high mobility, it is very hard to achieve reliable multicasting. Moreover, in the multihop sensor networks, unnecessary data forwarding activities occur frequently and they cause interference.According to our taxonomy [1], the existing reliable multicast schemes can be classified into ACK, NAK, or both. In the ACK-based scheme [2, 3], a source node should receive ACKs from all receivers to guarantee full reliability. However, if there are a large number of receivers located in the source, it will cause significant contention in the wireless channel. On the other hand, in NAK-based scheme, a receiver transmits NAK frame when it does not receive data frame [4]. However, NAKs cannot handle the unique cases in which all frames are lost at a particular node in the network. In the hybrid scheme, a transmitter elects a broadcast group leader. Non-leader receivers use the NAK-based scheme, while the leader uses an ACK-based scheme [5]. However, it will fail if the leader receives a frame successfully while all of the other receivers do not.By the above taxonomy approach, the proposed scheme is classified as ACK-based scheme because it provides full reliability. However, in densely deployed sensor networks, the ACK-based scheme will cause ACK implosion problem as mentioned earlier [1]. To compensate for this disadvantage, we develop a customized ACK (called pre-ACK) and implement an additional procedure. The pre-ACK transmission could provide fully reliable multicasting and decrease unnecessary data forwarding. When a receiver node overhears a multicast frame, the pre-ACK is used to announce its reception of the multicast frame to neighboring nodes which then do not need to duplicate the same multicast frame to it.The remainder of this paper is organized as follows. We survey the existing related work in Section2. In Section 3, we describe the proposed reliable multicasting algorithm, and the mathematical analysis is provided in Section 4. Section 5 evaluates the performance of our scheme in comparison with other legacy techniques. Finally, in Section 6, we draw conclusions.


## 2. Related Work and Contributions

The reliable multicasting schemes have been classified into ACK, NAK, or hybrid. One of the ACK-based schemes, a slot-reservation-based reliable broadcast protocol, was proposed to compensate the existing multicast scheme for lack of reliability [2]. In this scheme, a source node should receive ACKs from all receivers to guarantee full reliability. However, if there are a large number of receivers located in the source, the ACKs from the receivers should be collided in the wireless channel. Another ACK-based scheme called the round-robin acknowledge and retransmit (RRAR) scheme tries to reduce the above problem [3]. In this scheme, a sender requires a group acknowledgement from one of its neighbors after multicasting. This RRAR scheme is operated in a round-robin fashion for all receivers. Since only one of the receivers transmits ACK frame, the ACK implosion problem can be reduced. However, it cannot guarantee the reliability of all nodes when a large number of receivers are deployed.On the other hand, NAKs are transmitted when receivers do not receive multicast frame due to network failure. NAK-based scheme is well established under reliable channel condition (the loss probabilities are not high). Cooperative loss recovery for reliable multicast in ad hoc networks [4] is a NAK-based scheme, in which the NAK frames are transmitted after random durations to avoid NAK collision. Since one NAK is sufficient for the sender to be aware that an error has occurred, retransmission of the original frame also informs the receivers of later NAK timers to suppress their scheduled NAKs. In [6], the authors proposed another NAK-based scheme which should adaptively change coding scheme according to the link quality. However, NAKs cannot handle the unique cases in which all frames are lost at a particular node in the network. In such networks, the NAK frame also can be lost and the sender will be confused that transmitted data frames are successfully delivered to all receivers. Because of the above problems, ACK or NAK has not been used for multicasting services in military sensor networks.To tackle the above problems, a hybrid scheme that uses both ACK and NAK has been proposed [5]. In this scheme, a transmitter elects a broadcast group leader. To cope with the ACK implosion problem, non-leader receivers use the NAK-based scheme, while the leader uses an ACK-based scheme. However, this scheme still does not work in all cases; it will fail if the leader receives a frame successfully, while all of the other receivers do not.Moreover, the aforementioned schemes were proposed for static network topology and single-hop transmission. In the military sensor networks, the sensors are densely located and they forward redundant multicasting data frame due to high mobility. Therefore, the above schemes are not suitable for the military networks. In this paper, to resolve the above problems, we propose a reliable multicast protocol for military sensor network. The proposed reliable multicasting scheme uses a pre-ACK where it provides full reliable transmission in densely deployed sensor nodes. In cooperation with an additional procedure, the scheme can also reduce unnecessary data transmission in the multihop environment. As a result, the transmission collision among sensor nodes is downgraded significantly.


## 3. Reliable Multicasting Algorithm

In this paper, we assume a multihop topology in which all sensor nodes maintain their routing tables to forward data frames. Each routing table has a maximum number of entries (denoted byM). To release routing table cost, we use routing table management technique. If the routing table of a node is full, it chooses a neighbor node which has the shortest distance in its routing table. Then, it deletes that entry and broadcasts a network reconfiguration frame to its multicasting group. When sensor nodes receive this frame, they try to find another path except the previous path. Sensor nodes establish a group by peering procedure (as in Figure 1). In these networks, sensor nodes in the same multicasting group communicate with each other. For instance, if node A has multicast data it transmits the frames to all of nodes B and C (nodes B and C are the same multicasting group 1 with node A).Figure 1
A typical example of sensor networks; each sensor node maintains its routing table in order to allow multihop transmission and sensor nodes to establish their multicasting group.If a sensor node receives a multicast data frame, it has to decide to forward the frame or not. The sensor node compares the source and next-hop addresses with entries of its routing table. If it finds one or more next-hop entries which are not overlapped with the source address and those next-hop entries have the same multicasting group with the received frame, the sensor node forwards the incoming data frame to other sensor nodes. Otherwise, it does nothing.For instance, in Figure1, we assume that sensor node A multicasts data frame to group 1 (nodes A, B, C, D, and F belong to group 1). Sensor node B receives the data frame and compares source address of the received frame and next-hop address with entries in its routing table. If B finds any routing entry matches with the source address, it searches another routing entry that has the same multicasting group with different next-hop address field. Since node B has a routing entry (node D) to forward, it relays multicasting frame. The multicasting data frame is delivered to node F and node F does not forward the multicast data frame because there is no entry to forward.Normally in ACK scheme, to guarantee the reliability of data transmission between sensor nodes, all receivers must acknowledge the receipt of the frame from the transmitter. In above networks, relay nodes such as nodeB or D should receive ACK frames from nodes D and F, respectively. However, this scheme will cause severe network degradation due to unnecessary data retransmission in several network topologies. Figure 2 describes this network degradation. We assume that 4 nodes (S, A, B, and C) belong to the same multicasting group and each sensor node maintains its routing table. Even if nodes B and C are neighboring nodes with node S, they do not have routing entry for node S. For example, in network configuration stage, they are far away more than 1-hop from node S. However, after that they can be close to node S due to their mobility. At T=t0, node S multicasts to its neighbor nodes A, B, and C and waits for ACK frame from only node A (Figure 2(a)). Then, node A forwards the received data frame to node B and transmits ACK frame to node S (T=t1). At T=t2, node B forwards the multicast data to node C and transmits ACK frame to node A. Lastly, node C receives multicast data and acknowledges to node B (T=t3).Figure 2
An example of unnecessary multicasting data transmission.
(a)
T
=
t
0
(b)
T
=
t
1
(c)
T
=
t
2
(d)
T
=
t
3As observed in the above example, the ACK poses unnecessary long chain of data transmission. Even if we assume reliable links, unnecessary data transmission occurs (nodesA, B, and C already received multicast data at T=t0).To resolve the above problem, we proposed pre-ACK scheme. Once a sensor node overhears a multicasting data frame and the source address of received frame is not included in its routing table, the node transmits pre-ACK to the neighbor nodes which are in the routing table.Pre-ACK includes(1) originator address of data,(2) sequence number of data, and(3) address of receiver. Also, in the proposed scheme, we use ACK table where it indicates whether neighbor nodes successfully receive transmitted data frame or not. If all receivers in the ACK table are acknowledged, the node does not forward the data frame any more.Algorithm1 shows the pseudocode for proposed pre-ACK scheme. Let Fa and Ei denote the source address of received frame and routing entry of node i, respectively. In the proposed scheme, if node i receives multicasting data frame, it checks whether Fa is in a routing entry or not (lines 4-5). If Fa is in a routing entry of node i, the ACK table index Fa is set to 1, because receiving multicasting data frame is considered as an implicit ACK (line 6). Then, if there are other entries that are 0 in Ei, the node relays multicasting data to these nodes (lines 7-8). Otherwise, it transmits ACK frame to Fa (lines 9-10).Algorithm 1:Proposed reliable multicasting algorithm.
(1)  Fa  ←  the source address of received frame
(2)  Ei  ←  the routing entry of node i
(3)  loop
(4)  if  receives multicasting data frame  then
(5)   if  Fa is a routing entry of node i  then
(6)    ACK table index Fa is set to 1; {implicit ACK}
(7)    if there are other entries in Ei are 0 then  {relay case}
(8)     relays multicasting data to these nodes;
(9)    else  {non-relay case}
(10)    transmits ACK frame to Fa;
(11)   end if
(12)  else if  Fa is in the same multicasting group of i  then
(13)   transmits pre-ACK frame to all nodes in routing table;
(14)  else
(15)   discards received frame;
(16)  end if
(17) else if receives pre-ACK frame then
(18)  if  Fa is in a routing entry of node i  then
(19)   ACK table index Fa is set to 1;
(20)  else
(21)   discards received frame;
(22)  end if
(23) else  {received ACK frame}
(24)  ACK table index Fa is set to 1;
(25) end if
(26)  end loopOn the other hand, if there is no entry forFa in node i’s routing table and Fa is a member of the same multicasting group, it transmits pre-ACK frame to all nodes in routing table to limit unnecessary duplicate data transmission (lines 12-13). When node i receives pre-ACK frame, it sets index Fa of ACK table to 1 if Fa is in a routing entry of node i (lines 17–19). If it receives ACK frame, it also sets 1 to ACK table index Fa.Figure3 is an example scenario for the proposed scheme. Here, node S is the originator node and nodes A, B, C, D, and E are in the same multicasting group of node S. At T=t0, node S multicasts to its multicasting group members. However, nodes B, C, and D also overhear multicasting data frame as in Figure 3(a). In this scenario, we assume that node E cannot overhear the data frame due to network environment such as channel condition or collision. In Figure 3(b), node A transmits ACK frame to node S and forwards data frame to node B. At this time, nodes B and C also transmit pre-ACKs to their neighbor nodes (we assume that node C’s pre-ACK cannot be delivered to node B). Nodes A, B, C, D, and E receive pre-ACK from their neighbor nodes and update its ACK tables. At T=t2, there are some entries to forward multicasting data because nodes B and D do not know whether nodes C and E successfully receive data frame or not. Then, nodes B and D retransmit multicasting data frame to C and E, respectively. Lastly, nodes C and E transmit ACK frames to nodes B and D respectively and the whole ACK table is checked.Figure 3
Example of pre-ACK transmission scheme.
(a)
T
=
t
0
(b)
T
=
t
1
(c)
T
=
t
2
(d)
T
=
t
3


## 4. Analysis of the Proposed Scheme

In this section, we provide a mathematical model to measure the network throughput in cases of the proposed scheme which uses pre-ACK. To measure the network throughput, we design the discrete-time Markov chain (DTMC) model along with assuming a finite number of nodes. We discuss one such model that obtains saturated throughput. Figure4 shows the state transition process of a node represented by a discrete-time Markov chain model. Let the steady-state probabilities of the Markov chain be denoted by Si, St, Sw, Sk, Sr, Sp, and Sa where i, t, w, k, r, p, and a represent state of “idle,” “transmit multicast data,” “wait for ACK,” “transmit ACK,” “receive multicast data,” “receive pre-ACK,” and “transmit pre-ACK,” respectively.Figure 4
State diagram of the proposed scheme.Then we need to derive the transition and steady-state probabilities. First, we obtain the steady-state probabilities from Figure4 as (1)St=pitSi+pptSp+pwtSw+prtSr,Sw=ptwSt,Sp=pipSi,Sr=pirSi,Sa=praSr,Sk=prkSr,Si=pkiSk+pwiSw+ppiSp+paiSa.Next, we need to calculate the transition probabilities. First, we can derivepit as (2)pit=τ,where τ denotes the probability that a node transmits in the backoff stage. This can be calculated using the backoff Markov chain model from [7] and τ can be calculated as follows:(3)τ=21-2p1-2pW0+1+pW01-2pk,where p and W0 denote the collision probability and maximum backoff window size for stage 0, respectively. k denotes the number of backoff stages.Next, we can deriveppt as(4)ppt=PThere are routing entries to forward=1-1Mi12+1-1-pMi-112,where Mi denotes the number of routing entries.Similarly, we can derivepwt and prt as(5)pwt=PTransmitted frame is collided=p,prt=PThere are routing entries to forward=1-1Mi12+1-1-pMi-112.Since we assume that all of the frames except the data frame are delivered successfully,ptw, pki, and pai are 1.Then, we can derivepip as(6)pip=p1p2,where p1=P{neighbornode transmits a pre-ACK} and p2=Psource is a member of multicasting group. Then, we can obtain p1=τ(1-Mi/N) and p2=Mi/N, where N is the number of neighbor nodes. Similarly, we can obtain(7)pir=τ1-τN-1.Next, we can derivepra as(8)pra=Pthere is no entry for source address=1-MiN.Also, prk can be calculated as(9)prk=MiN1-1Mi.By solving the balance equation for the steady-state probabilities, we can obtain each steady-state probability as(10)Sp=τ1-MiNMiNSi,(11)Sa=1-MiNSr,(12)Sr=τ1-τN-1Si,(13)Sk=1-1MiMiNSr,(14)St=τSi+1-1Mi12+1-1-pMi-112·τ1-MiNMiNSi+pSt+1-1Mi12+1-1-pMi-112·τ1-τN-1Si=Sw.Thus, according to (2)–(13), all of the steady-state probabilities are expressed as Si, which is finally determined by imposing the normalization condition that is simplified to (15)Si+Sw+Sk+St+Sr+Sp+Sa=1.We denote the time period during which a node is in the corresponding states byTi, Tw, Tk, Tt, Tr, Tp, and Ta. Since we assumed a full buffer model for each node, there is no waiting time for data arrival from the upper layer. Therefore, the expected time in the idle state, denoted by ETi, can be calculated as(16)ETi=DIFS+αW0+12,where α denotes a backoff slot time duration. Similarly, expected time in each state can be calculated as follows:(17)ETp=SIFS+pre-ACKη=ETa,ETt=SIFS+DATAη=ETr,ETk=SIFS+ACKη,ETw=δ,where pre-ACK, DATA, η, and δ denote the size of pre-ACK, multicast data frame, data rate, and ACK timer, respectively.Lastly, we can calculate the network throughput for proposed scheme. Then, the throughput of a network withN nodes is given by (18)TH=NSrEPSiETi+SwETw+StETt+SpETp+SaETa+SkETk+SrETr.Figure5 shows the aggregate throughput analytical result. We compare our proposed scheme with ACK-based multicasting scheme. We observed that the aggregate throughput achieves the best performance when the number of nodes is 4~5. This is mainly because increasing the number of nodes increases the interference of each ongoing communication. Moreover, our proposed scheme outperforms ACK-based scheme by limiting unnecessary data transmission. As a result, our scheme can reduce the number of collisions between sensor nodes.Figure 5
Aggregate throughput versus the number of sensor nodes. (We assume all sensor nodes have full buffer.)


## 5. Performance Evaluation

To evaluate our proposed scheme, we developed network scenarios based on OPNET simulator. The simulation parameters are listed in Table1. To measure the effectiveness of the pre-ACK scheme, we evaluated the areal sum throughput which is the total number of packets received by all sensor nodes and energy consumption which is the total energy consumption of all nodes divided by the number of transmitted frames. To evaluate the effectiveness of proposed scheme, we compared the performance of the pre-ACK scheme with normal-ACK-based scheme using OPNET simulation. Also, we have three scenarios. In Scenario 1, the topology size is 50 m × 50 m and all sensor nodes are located in 1-hop range. In Scenario 2, the topology size is also 50 m × 50 m and maximum hop range is 2-hop. Lastly, in Scenario 3, all sensor nodes are uniformly distributed in 500 m × 500 m and maximum hop range is 10-hop.Table 1
Simulation parameters.
Parameters
Value
Transmission type
Multicast
Number of groups
1
Topology size
Scenarios 1, 2: 50 m × 50 mScenario 3: 500 m × 500 m
Number of nodesData rate
1~51210 Mbps
Data arrival rate
Scenario 1: full bufferScenarios 2, 3: 2 frames/sec
DropCWMinCWMax
2-stage drop24 210
DIFS
50µs
SIFS
20µsFigure6 shows the areal sum throughput versus the number of nodes. In our proposed scheme, the throughput has 2.1 × 104 Mbps/km2 while it has 2.6 × 104 Mbps/km2 in the ACK-based scheme when the number of nodes is 512. ACK-based scheme achieves the best performance since there is no collision in this scenario. In our proposed scheme, ACK frames collided among the receivers. The throughput of the proposed scheme is 20% less than the ACK-based scheme when the number of nodes is 512 due to ACK overhead.Figure 6
Aggregate throughput versus the number of sensor nodes (Scenario 1).Figure7 shows the areal sum throughput in Scenario 2. In both of the schemes, the throughput increases as the number of nodes increases. It is different from Scenario 1; the proposed scheme has throughput higher than ACK-based scheme’s since the transmitted data collided among transmitters. The throughput of the proposed scheme is 3% higher than the ACK-based scheme when the number of nodes is 250 and the number of transmitters is 8. The reason is that ACK-based scheme does not provide retransmission function when a data frame is collided.Figure 7
Aggregate throughput versus the number of sensor nodes (Scenario 2).Figure8 shows the areal sum throughput in Scenario 3. In our proposed scheme, the throughput increases as the number of nodes increases. However, the throughput of ACK-based scheme decreases after the number of nodes is 250 since ACK frames collided more, and hidden node problem occurs in this scenario. Also, if a relay node does not receive any data frame, it does not forward data frame anymore in the No-ACK-based scheme. Pre-ACK technique can reduce the transmitted ACK frames.Figure 8
Aggregate throughput versus the number of sensor nodes (Scenario 3).Figure9 shows the energy consumption versus the number of nodes in Scenario 3. As shown in the figure, the energy consumption increases as the number of nodes increases in ACK-based scheme. This is because there are more data and ACK collisions in this scenario. We observe that our pre-ACK scheme is more energy-efficient than ACK-based scheme.Figure 9
Energy consumption per frame versus the number of sensor nodes (Scenario 3).


## 6. Conclusion

Wireless sensor networks have drawn attention for military applications where a large number of light-weight sensor nodes are used to detect enemy and transmit sensed information to sink node. In particular, QoS is one of the most important requirements to support their mission-critical applications. However, to achieve a reliable multicasting transmission is very hard because sensor nodes are densely located and the native behavior of wireless communication is unpredictable due to high mobility. Moreover, in the multihop deployed sensor networks, redundant data forwarding occurs frequently and it causes interference among the nodes. In this paper, we proposed an efficient reliable transmission scheme using pre-ACK frames to provide full reliability multicasting data transmission and decrease unnecessary data forwarding activities in the military sensor networks. In our scheme, the ACKs are exchanged periodically to verify the availability of adjacent nodes and the pre-ACK transmission is used to prevent redundant frames between neighbor nodes. The performance evaluation shows that the pre-ACK-based scheme outperforms the existing ACK-based schemes in terms of the aggregate throughput and energy consumption.



---

*Source: 341912-2015-08-25.xml*