Sage Journals: Discover world-class research

Abstract

In wireless multihop bidirectional communication environment, there is a possibility that packet collision and retransmission owing to the hidden node problem decrease efficiency of throughput. The aim of this article is to achieve efficient and reliable packet transmissions in such environments. To do so, we propose a packet transmission scheme named inter-flow network coding with passive acknowledgment. In inter-flow network coding with passive acknowledgment, it is necessary to optimize the encoding latency and to avoid passive acknowledgment packet collision, so we address these issues in this article. Finally, we also confirm that the inter-flow network coding with passive acknowledgment scheme is effective in terms of the collection ratio and delay through simulations.

Keywords

Wireless multihop network bidirectional communication hidden node problem inter-flow network coding passive acknowledgment

Introduction

In a multihop wireless local area network (LAN) or a wireless sensor network, packets are transmitted from the source node to the destination node by relay from one wireless station (node) to another or “multihop transmission.” The advantages of wireless multihop transmission are that it allows the transmission to a node which cannot be directly reached from the source node and that it does not require base stations or other transmission infrastructure. This is why it is being considered for use over a wide variety of applications, including smart meters, structure monitoring, and disaster response. Market-ready systems are being prepared on the basis of countless R&D efforts and validation tests. Among these applications are, for example, the disaster response system^1,2 based on a wireless sensor network described in section “Evaluation of practical applications by simulation,” in which data packets are directed from the sensing nodes to multiple data collection nodes (sinks). This system contains sensors and actuators and collects sensing data from the nodes and transmits signals to operate actuators. Thus, its paths are quite busy with traffic in both directions.

However, in a multihop wireless network based on IEEE 802.11 standard³ for wireless LANs or IEEE 802.15.4 standard⁴ for wireless sensor networks, a flow of traffic in both directions over the paths may degrade throughput due to the hidden node problem.⁵ In medium access control (MAC) of these standards, carrier sense multiple access with collision avoidance (CSMA/CA) is employed. Under CSMA, since any transmitting stations outside carrier sense range do not detect packet transmissions by other stations, it is possible for any one such station to transmit regardless of the fact that another station is already in the process of transmission. This causes packet collision and is called “the hidden node problem”; the colliding packets must be retransmitted, and this drastically slows throughput as a result. One of the ways to mitigate this problem is to reduce the number of packet transmissions.

“Network coding” (NC)⁶ is expected to reduce the number of packet transmissions. A form of NC in which packets in different network flows are encoded by relay nodes is called inter-flow network coding (IFNC).^7,8 In this article, with the objective of enabling highly efficient and reliable packet transmission in bidirectional communication environments, a scheme referred to as IFNC with passive acknowledgment (IFNCPA) is proposed here; this scheme is a packet transfer protocol combining IFNC and passive ACK.⁹ This article combines the information of two previous technical reports^10,11 with the results of an evaluation of the new capabilities under the proposed scheme to demonstrate that the proposed scheme improves the transmission and efficiency.

As described in section “Preparations and issues,” when packets encoded using IFNC are broadcasted to neighboring nodes (the next-hop nodes), if the broadcast packets are not accurately received, there is no way for the transmitting node to “know” that because a broadcast packet is not usually acknowledged. Since the packets are not retransmitted, the transmission reliability is degraded. The transmission simulation results described in section “Parameter tuning and basic evaluation” also support this, showing that during sequential unicast transmission of packets under only IFNC, the collection ratio is lower than under multihop transmission.

COPE¹² is known as the first practical implementation for wireless mesh networks. COPE is located between the MAC layer and the Internet Protocol (IP) layer. COPE header is inserted between the IP header and the MAC header. By including ACK blocks in the COPE header, an adjacent node is notified of reception of the encoded packet. BEND¹³ incorporates the function of IFNC into the MAC layer of IEEE 802.11. For the sake of this, the IEEE 802.11 MAC header needs to be modified. In BEND, a modified ACK frame is sent to notify of reception of the encoded packet. These ACK mechanisms for encoded packets lead to overhead. Several variants of COPE and BEND have been proposed to enable more coding opportunities and increase network capacity, for example, DCAR,¹⁴ CORE,¹⁵ DODEX+,¹⁶ INCP,¹⁷ and FlexONC.¹⁸ These schemes can be regarded as inheriting the ACK mechanism of COPE and BEND, and none of them utilizes passive ACKs.

Dualcast transmission¹⁹ is another approach for the exchange of ACK packets rather than the multicast transmission in order to compensate for degradation in reliability in IFNC. It is no easy matter to extend the MAC layer, which must be done for dualcast transmission, making it difficult for practical application. In contrast, employing passive ACK, which provides confirmation by monitoring packet relay by the next-hop node, the IFNCPA scheme attempts to compensate for the reduction in reliability in broadcast transmission, with no necessity to extend the MAC layer at all.

As explained in section “Preparations and issues,” IFNC inherently has the function of implicit passive ACK for encoded packets, which is not fully utilized in the previous studies. In IFNCPA, passive ACK is also applied to native packets, that is, unencoded packets. This IFNCPA scheme is not merely a combination of IFNC and passive ACK. As section “Preparations and issues” will show, the encoding latency must be set to the proper interval, and the issue of collision of passive ACK packets must be avoided. Therefore, a combination of systems is examined in this study. One system determines the encoding latency dynamically using the intervals between arriving packets from previous counterflow data, and the other avoids passive ACK packet collision by determining the best offset for the shifts the timing of transmission of one or the other neighboring nodes which have received an encoded packet.

This article is organized as follows: section “Preparations and issues” gives an overview of the IFNC scheme and passive ACK and related issues and section “Details of IFNCPA scheme” presents the details of the IFNCPA scheme. Section “Parameter tuning and basic evaluation” traces the process of parameter tuning and presents a basic evaluation using a simulation of a linear network topology. Section “Evaluation of practical applications by simulation” provides another evaluation by simulation whose scenario features a disaster response system as a practical application of the IFNCPA scheme. Section “Conclusion and remarks” is a summary of our results.

Preparations and issues

The IFNCPA scheme is a combination of IFNC and passive ACK. This section presents an overview of IFNC and passive ACK and two issues related to these schemes.

IFNC

Let us describe XOR (eXclusive OR) operations, which reduces the number of transmitted packets, using the simplest example of IFNC. Figure 1 shows an example in which $N_{2}$ is a relay node through which both packet $a$ from node $N_{1}$ bound for node $N_{3}$ and packet $b$ from $N_{3}$ bound for $N_{1}$ pass. Below, a packet obtained by the XOR operation performed on the two packets $a$ and $b$ is denoted by $a \oplus b$ and called the “encoded packet.” Here, “XOR operations” means that the “exclusive OR” logical operation is carried out for each bit of the data portion of the packets. Note that $a \oplus b$ and $b \oplus a$ are equivalent mathematically. In what follows, however, let notation $a \oplus b$ mean that $a$ is received earlier than $b$ by a relay node, for example, $N_{2}$ in Figure 1(b), as explained below.

Figure 1.

Reduction in transmitted packet by XOR operation: (a) unicast and (b) IFNC.

Figure 1(a) depicts the case of ordinary packet relay by simple unicast transmissions. Figure 1(b) depicts the case of IFNC using the XOR operation, in which the encoded packet is transmitted by broadcast. In Figure 1(a), $N_{2}$ relays the received packets $a$ to $N_{3}$ and $b$ to $N_{1}$ ; thus, $N_{2}$ performs two unicast transmissions. Figure 1(b) shows just a single broadcast of a new encoded packet $a \oplus b$ generated by the XOR operation on the received packets $a$ and $b$ from $N_{2}$ . (Recall notation $a \oplus b$ means that $a$ is received earlier than $b$ by a relay node, i.e. $N_{2}$ as mentioned above.) Thus, this has a clear advantage in the efficiency of packet propagation from $N_{2}$ to other nodes within range.

$N_{1}$ can extract packet $b$ from the received encoded packet $a \oplus b$ and packet $a$ , which it has transmitted and still holds, as a result of $b = (a \oplus b) \oplus a$ . $N_{3}$ can do the same to obtain packet $a$ . Thus, it is possible to reduce the number of packet transmissions using IFNC, and we can expect improvement of the throughput from this.

As a side effect, however, broadcasting the encoded packets can lower reliability. In general, under MAC schemes like IEEE 802.11 and IEEE 802.15.4, ACK is not required in broadcast or multicast transmission, in contrast to a unicast transmission. This is because simultaneous ACKs from multiple receiving nodes would collide and it fails to properly verify receipt of packets. Therefore, even if the encoded packets are not accurately received, the relay node, say $N_{2}$ in Figure 1(b), cannot know that. In order to deal with this problem, passive ACK and explicit ACK can be utilized as explained in section “Passive ACK.”

Note that, for the XOR operations, each node equips with two types of buffers. For example, in Figure 1(b), after transmitting $a$ , $N_{1}$ keeps the data of $a$ to extract another data $b$ from an encoded data $a \oplus b$ which are made from $a$ . For the sake of this, each node has a “decoder buffer” to hold transmitted data. Also, since receiving a packet $a$ , $N_{2}$ keeps the data of $a$ because it may have a chance to generate an encoded packet, say $a \oplus b$ , where $b$ is directed to the node which sent $a$ to $N_{2}$ itself. For the sake of this, each node has an “encoder buffer” to hold received data.

Issue 1: determining the appropriate encoding latency

An encoded packet is generated from two packets. The node that has a packet to be relayed cannot wait forever for the arrival of another packet. In the example in Figure 1(b), $N_{2}$ holds packet $a$ once received it and must then wait for packet $b$ to arrive in order to utilize NC for a while. The longer this interval, the later packet $a$ arrives at node $N_{3}$ . In order to suppress this delay, encoding latency is introduced. The relay node sends each incoming packet to be relayed to the next-hop node by unicast transmission if no new packet arrives from counterflow by the expiration of the waiting timer for encoding latency.

Too long interval, however, possibly leads to large latency in the case of a few counterflow packets as shown in Figure 2(a). On the other hand, too short interval reduces the opportunities for encoding packets and results in little improvement in transmission efficiency as shown in Figure 2(b). Thus, the best policy is to wait the usual interval between packet arrivals from counterflow, as long as the encoding latency is not too long. It is essential to have a scheme for determining the appropriate encoding latency.

Figure 2.

Issue on encoding latency: (a) long waiting time interval and (b) short waiting time interval.

Passive ACK

The IFNCPA scheme utilizes passive ACK in order to compensate for the reduction in reliability of broadcast transmission of encoded packets in the IFNC scheme.

Passive ACK is a scheme for each node to passively verify that its packets have been correctly transmitted by observing the relay transmission by a neighboring node (next-hop node). In Figure 3, node $N_{3}$ broadcasts packet $c \oplus a$ , so that node $N_{2}$ can not only extract packet $c$ from it and packet $a$ hold by itself using XOR operations but also implicitly (or passively) know that packet $a$ has been correctly received by the neighboring node $N_{3}$ . In this sense, IFNC inherently has the function of implicit passive ACK for encoded packets. In this figure, $N_{2}$ sends packet $c$ to $N_{1}$ in a unicast transmission since waiting timer for encoding latency expired. At this time, node $N_{3}$ can also passively know that packet $c$ has been received by node $N_{1}$ by overhearing this unicast transmission. When the packet cannot be monitored by the retransmission time-out (RTO) from the next-hop node, this is interpreted as meaning that the packet was not accurately received for some reason and the packet is re-sent; this process maintains transmission reliability. In this way, IFNCPA aims to exploit the nature of passive ACK.

Figure 3.

Passive ACK and explicit ACK.

Note that passive ACK is only used when the receiving node relays the packet on. For example, when the receiving node is a (final) destination, it will never further relay the packet. In such a case, the receiving node needs to generate an ACK packet (namely, “explicit ACK”) in a layer higher than MAC layer and send by unicast like $N_{1}$ and $N_{4}$ in Figure 3; this mimics the standard ACK packet in MAC layer.

Issue 2: avoiding collisions of passive ACK packets

A preliminary simulation clearly showed that if IFNC and passive ACK are simply combined, the passive ACKs often collide, defeating the purpose of verifying receipt of packets.¹¹ Through the analysis of the simulation results, there were often observed two cases as shown in Figures 4 and 5.

Figure 4.

Passive ACK collision case 1.

Figure 5.

Passive ACK collision case 2.

Let us begin with an explanation of case 1, shown in Figure 4. Nodes $N_{2}$ and $N_{4}$ receive and hold packets $d$ and $c$ , respectively. Next, while holding $a$ and $b$ , respectively, $N_{2}$ and $N_{4}$ each receive the encoded packet $a \oplus b$ from $N_{3}$ , carry out the XOR operation, and extract $b$ and $a$ , respectively, therefrom. Next, $N_{2}$ and $N_{4}$ encode $d \oplus b$ and $c \oplus a$ using extracted data of $b$ and that of $a$ , respectively, and immediately broadcast these; as a result, these packets collide at $N_{3}$ . Thus, $N_{3}$ is unable to monitor these encoded packets and cannot confirm whether packet $b$ arrived at $N_{2}$ or packet $a$ arrived at $N_{4}$ . That is, $N_{3}$ fails to receive the passive ACKs. This situation can occur more frequently in the case of the higher offered load. In order to avoid this, as explained later using Figure 8, one of the nodes that received the encoded packet needs to shift the next action such further relaying like $N_{2}$ or returning an ACK message like $N_{1}$ .

Case 2 is described using Figure 5. Nodes $N_{2}$ and $N_{4}$ receive the encoded packet $a \oplus b$ from $N_{3}$ ; they perform the XOR operation using packets $a$ and $b$ , which they had earlier transmitted and stored, to extract packets $b$ and $a$ , respectively. In this case, the waiting timers for encoding latency expire, and $N_{2}$ and $N_{4}$ transmit packets $b$ and $a$ to $N_{1}$ and $N_{5}$ , respectively, in the unicast mode. Then, as shown in the figure, when the difference between the encoding latency of $N_{2}$ and $N_{4}$ is shorter than the packet transmission delay, packet $b$ sent by $N_{2}$ and packet $a$ by $N_{4}$ collide at $N_{3}$ . Thus, $N_{3}$ is unable to verify that packet $b$ arrived at $N_{2}$ or $a$ arrived at $N_{4}$ correctly. This situation can occur more frequently in the case of the lower offered load. In order to avoid this, as explained later using Figure 9, nodes that received the encoded packet need to have encoding latency different by at least one packet transmission delay.

Details of IFNCPA scheme

To our best knowledge, the two issues described in section “Preparations and issues” have not been addressed in the past research. This section proposes the IFNCPA scheme, which incorporates measures against these issues. The approach for the first issue is described in section “Determining the appropriate encoding latency and time-outs.” For the second issue, the offset mechanism to avoid collisions of passive ACKs is introduced as described in section “Basic idea to avoid passive ACK collisions.”

In what follows, we assume that the IFNCPA scheme is installed on the application layer to make it more convenient to use, and it is assumed that the User Datagram Protocol/Internet Protocol (UDP/IP) is employed to access it on lower layers. Therefore, “message” is interchangeably used with “packet” hereafter. The IFNCPA scheme would also be possible to install it on the network layer and avoid the use of IP. Passive ACK was established by operating the MAC layer in promiscuous mode so that MAC frames not addressed to the monitoring node could be monitored.

Message format

Figure 6 provides an example of the format of a data message in the IFNCPA scheme (a protocol data unit (PDU) on the application layer). An encoded data chunk is generated by the XOR operation from two native data chunks and the result is stored in the data field of an encoded message. In order to guarantee this operation, the data chunk is of a fixed length. The encoded data must be associated with the identifier (ID) of the native data chunk. Two fields, ID1 and ID2, in the message are reserved to store this ID. Each ID consists of the following: the IP address of the source node of the native data chunk (in other words, the node where the data were generated), the IP address of the destination node, and a sequence number attached to the data chunk by the source node. The data chunk is uniquely identified by these. Note that the data message itself is of a fixed length since the ID field is also of a fixed length, for example, 10 octets as shown in Figure 6.

Figure 6.

Data message format of IFNCPA.

The first field ID1 of the encoded data message holds the ID of the native data previously received and kept in the encoder buffer to hold received data, and the second field ID2 holds the ID of the native data received subsequently and appropriate for the relay. For example, in Figure 1, ID1 and ID2 of the encoded message $a \oplus b$ correspond to ID of $a$ and that of $b$ , respectively. When the data field includes only a native data chunk (i.e. non-encoded data message), its ID is stored in ID1 field and all the bits in ID2 are set to 0. Thus, examining ID2 reveals whether any of the content of the data fields has been encoded.

For simplicity, we assumed that the message size is a fixed length. In fact, however, the XOR operation is applicable for variable message length if a message length field is introduced in ID format. Suppose that data chunk $a$ of $l_{a}$ octets and $b$ of $l_{b} (\geq l_{a})$ octets are encoded into chunk $a \oplus b$ , whose length is $l_{a}$ octets. In this case, chunk $a$ can be simply extracted as $a \oplus (a \oplus b)$ . On the other hand, chunk $b$ can be obtained as the most significant $l_{b}$ octets of $b \oplus (a \oplus b)$ . Performance evaluation in the case of heterogeneous message length is left for further study.

Transmission on MAC/PHY layer

Recall that a data message is a PDU on the application layer. When a message which includes encoded data chunk is transmitted, its destination IP address is set to the broadcast IP address. Thus, the destination MAC address also becomes the broadcast MAC address, and broadcast transmissions are executed on the MAC layer. The IP address of the destination node for the data chunk is stored in the ID field, so this information is never lost. As a result of this broadcast transmission, the message reaches an IFNCPA-type entity of the application layer of the neighboring node.

As shown in Figure 3, when the receiving node is a (final) destination, the IFNCPA-type entity replies an explicit ACK message, which is also a PDU on the application layer like a data message. An explicit ACK message includes only the ID of the data chunk to be acknowledged and it is sent in a unicast transmission to the neighboring node to be acknowledged.

In this study, the data rate of MAC is assumed to be the same among all nodes.

Communication model

In Figure 1(b), the relay node $N_{2}$ generates the encoded message $a \oplus b$ from message $a$ from $N_{1}$ to $N_{3}$ and message $b$ from $N_{3}$ to $N_{1}$ . In general, such messages that pass each other through a relay node can be encoded at the node. We call data chunks of these messages “encodable” there.

Let us generalize this to a communication model as shown in Figure 7. Here, we focus on node $N_{r}$ as a relay node, which has multiple neighboring nodes. Without any loss of generality, we select two of them, $N_{p}$ and $N_{n}$ , and consider data flow segment from $N_{p}$ to $N_{n}$ via $N_{r}$ denoted as “ $p \to n$ ” and its counterflow, that is, data flow segment from $N_{n}$ to $N_{p}$ via $N_{r}$ denoted as “ $n \to p$ ”. Here, “segment” means that $N_{n}$ and/or $N_{p}$ are not necessarily sources and/or destinations and they can be relay nodes for the flows.

Figure 7.

Communication model.

A native data chunk of $p \to n$ and that of $n \to p$ are encodable at $N_{r}$ . The encoded data message made from them can be regarded as “directed” to only $N_{p}$ and $N_{n}$ which receive or relay it even though the message is broadcasted on the MAC layer as explained in section “Message format.” In other words, the other neighboring nodes may ignore it. Taking the above into consideration, each node can determine whether or not the encoded data message is directed to itself by checking whether the message includes the native data chunk that it has transmitted.

Basic idea to avoid passive ACK collisions

Let us explain a mechanism to avoid passive ACK collisions as much as possible, the necessity of which was mentioned in section “Issue 2: Avoiding collisions of passive ACK packets,” referring again to Figures 4 and 5. This mechanism attempts to avoid collisions between messages for passive and/or explicit ACK by delaying the transmission of one message by the offset time as shown in Figures 8 and 9.

Figure 8.

Effect of offset to avoid passive ACK collision case 1.

Figure 9.

Effect of offset to avoid passive ACK collision case 2.

In this study, we assume that the length of data chunk and the data rate are both constant. Let $T_{o}$ denote the value of offset, that is, the time span by which transmissions are delayed as shown in Figures 8 and 9. This offset could make passive ACKs avoid a collision. Let $T_{tx}$ denote the transmission delay which is required to send one data message.

As shown in Figure 9, the timing of transmissions $N_{2}$ and $N_{4}$ must be shifted by at least $T_{tx}$ in order to avoid passive ACK collisions, so that $T_{o}$ must be greater than $T_{tx}$ . The value of $T_{o}$ will be discussed in section “Parameter tuning and basic evaluation.”

Transmission procedure

Regardless of an encoded message or a non-encoded message, the IFNCPA entity temporally stores the transmitted data chunk and the associated ID in its decoder buffer until it receives the corresponding ACK. Note that the data chunk and its ID stored in the decoder buffer are also used when the IFNCPA entity extracts native data chunk from a directed encoded data message.

In the case of the encoded data message, such as message $a \oplus b$ in Figure 3, the IFNCPA entity starts the retransmission timer for this message (described in section “Determining the appropriate encoding latency and time-outs”). Recall that the encoded data chunk is made from two native data chunks. Once an ACK is received by means of passive ACK or explicit ACK, the data chunk and its ID are deleted from the decoder buffer. However, if one or both of them have not received any ACK by RTO, the message is retransmitted and the timer is re-started. This is repeated if the number of (re)transmissions does not exceed the predetermined maximum limit. Otherwise, the data chunk and its ID are discarded from the decoder buffer. The value of RTO is discussed in section “Determining the appropriate encoding latency and time-outs.”

In the case of the non-encoded data message, such as message $a$ in Figure 3, the IFNCPA entity starts the retain timer for this message instead of the retransmission timer. This is because the transmitted data may be used for future decoding process, while the retransmission is left to the MAC layer since the non-encoded data message is unicast. The value of retain-time-out is also discussed in section “Determining the appropriate encoding latency and time-outs.”

Reception and relay procedure

When receiving an encoded data message, the IFNCPA entity determines whether it is “directed” to itself or not. If the encoded data message includes the native data chunk that the entity has transmitted and holds in the decoder buffer, the message is “directed” as explained in section “Communication model.” Then the entity extracts the native data chunk to be received or relayed by decoding from the message and the other native data chunk stored in the decoder buffer. Otherwise, the message is discarded since it is not directed. When receiving a non-encoded data message, the entity simply receives the native data chunk of the message since it is unicast.

The received native data chunk is concluded to arrive at the (ultimate) destination if the current node’s IP address matches the destination node’s IP address included in the ID associated with the native data chunk. Otherwise, the received native data chunk should be relayed, so that the next-hop node is determined according to the destination IP address based on the routing policy.

If the native data chunk is conveyed at the ultimate destination by the encoded data message, say $x \oplus y$ , an explicit ACK message for the native data chunk is unicast to the node that transmitted the message. If the native data chunk is $x$ , an explicit ACK message is replied immediately; otherwise, it is after the offset period $T_{o}$ (e.g. explicit ACK for $a$ and that for $b$ in Figure 8). If the native data chunk, say $y$ , to be relayed finds other native data chunk, say $x$ , stored in the encoder buffer, encodable with itself, the encoded message $x \oplus y$ is generated from them and broadcast immediately or after waiting for the offset time $T_{o}$ (described in section “Basic idea to avoid passive ACK collisions”). In the case where there are multiple encodable data chunks in the encoder buffer, the oldest one is chosen. Then, both the transmitted native data chunks are stored in the decoder buffer.

Immediate transmission is performed if either of two conditions holds: $y$ was received in a unicast transmission (e.g. $b$ and the resulting $a \oplus b$ at $N_{3}$ in Figure 8) or $x$ was extracted from another encoded message and the ID of $x$ was included in ID1 (e.g. $a$ and the resulting $c \oplus a$ at $N_{4}$ in Figure 8). Otherwise, the encoded message is sent after the offset period $T_{o}$ (e.g. $d \oplus b$ by $N_{2}$ in Figure 8). These rules, as shown in Figure 8, shift the timing of packet transmission between $c \oplus a$ and $d \oplus b$ by the offset $T_{o}$ , so that it is expected that packet collision is prevented.

If the native data chunk to be relayed cannot find other native data encodable with itself in the encoder buffer, it is stored in the encoder buffer along with the associated ID and IP address which were sent with it from the neighboring node. At the same time, the encoding latency timer is started for the native data chunk, as described in section “Determining the appropriate encoding latency and time-outs.” When the encoding latency for the native data chunk times out, it is unicast to the next-hop node immediately or after waiting for the offset time $T_{o}$ . Immediate transmission is performed if either of two conditions holds: the native data chunk was received in a unicast transmission or it was extracted from another encoded message and its ID was included in ID1 (e.g. $a$ in Figure 9); otherwise, it is after the offset period $T_{o}$ (e.g. $b$ in Figure 9).

Determining the appropriate encoding latency and time-outs

This section explains how to determine the encoding latency. As described in section “Issue 1: determining the appropriate encoding latency,” the best policy is to wait for the usual interval between packet arrivals from counterflow. However, a maximum value is set for the encoding latency to suppress the end-to-end delay to some extent.

Let us return to the communication model shown in Figure 7. Here, without any loss of generality, we focus on the $p \to n$ message flow and the $n \to p$ message flow, which are encodable at $N_{r}$ each other. The coding latency for a message of the $p \to n$ flow is determined according to the past arrival intervals of the $n \to p$ flow, and vice versa. Let $S_{i}^{n \to p}$ denote the arrival interval between the $(i - 1) st$ and the ith arrival messages of the $n \to p$ flow at $N_{r}$ , where $i \geq 2$ . Let ${\bar{S}}_{i}^{n \to p}$ and ${\bar{V}}_{i}^{n \to p}$ denote the exponentially weighted moving average (EWMA) of the arrival interval of the $n \to p$ message flow and that of its deviation, respectively. For $i > 2$ , they are recursively calculated as follows

{\bar{S}}_{i}^{n \to p} = α S_{i}^{n \to p} + (1 - α) {\bar{S}}_{i - 1}^{n \to p}

(1)

{\bar{V}}_{i}^{n \to p} = β | S_{i}^{n \to p} - {\bar{S}}_{i}^{n \to p} | + (1 - β) {\bar{V}}_{i - 1}^{n \to p}

(2)

where $α$ and $β$ are the smoothing coefficients, and ${\bar{S}}_{2}^{n \to p} = S_{2}^{n \to p}$ and ${\bar{V}}_{2}^{n \to p} = 0$ . In this article, employing the algorithm for estimating the round trip time (RTT) in the transmission control protocol (TCP),²⁰ $α$ and $β$ were set to $0.125$ and $0.25$ , respectively. Let $W_{i}^{p \to n}$ denote the encoding latency for the $p \to n$ messages which arrive at $N_{r}$ after the arrival of the ith $n \to p$ message and just before that of the $(i + 1) st$ one. In this article, in order to adjust the encoding latency to the arrival of the $n \to p$ message flow, we set

W_{i}^{p \to n} = min {{\bar{S}}_{i}^{n \to p} + γ {\bar{V}}_{i}^{n \to p}, W_{\max}}

(3)

where $γ$ is the encoding latency coefficient to add a margin and $W_{\max}$ is the upper limit of encoding latency to suppress the end-to-end delay even when $S_{i}^{n \to p}$ takes large values, that is, in the case of low traffic load in $n \to p$ message flow.

When passive ACK is employed, how long retransmission should be refrained from is an important issue. For example, the longer is the encoding latency of the neighbor nodes, the longer is the time to receive the passive ACK. The variables ${\bar{S}}_{i}^{n \to p}$ , ${\bar{V}}_{i}^{p \to n}$ , and $W_{i}^{n \to p}$ are updated every time $N_{r}$ receives a message of $n \to p$ flow. To represent the latest values of these variables, we omit the subscription $i$ from them, for example, $W^{p \to n}$ . Furthermore, let $R^{p \to n}$ denote the value of RTO for the $p \to n$ message flow, and let $R$ denote the common value of RTO of $N_{r}$ for the $p \to n$ and the $n \to p$ message flows. The neighbor node may postpone relaying messages by the coding latency, and the value of RTO should be slightly longer than the encoding latency. Given the neighbor node has a similar traffic flow in bidirectional communications, adjacent nodes could have similar encoding latency. With the above consideration and the reference to the RTO in TCP,²⁰ $R^{p \to n}$ of $N_{r}$ is set as the encoding latency $W^{p \to n}$ plus the quadruple of $V^{n \to p}$ as follows

R^{p \to n} = W^{p \to n} + 4 V^{n \to p}

(4)

$R^{n \to p}$ for the $n \to p$ message flow is also set in the same way. Since the encoded message is made from two native data chunks, $R$ is set to the larger of $R^{p \to n}$ and $R^{n \to p}$ , that is

R = max {R^{p \to n}, R^{n \to p}}

(5)

Parameter tuning and basic evaluation

This section describes the process of tuning the control parameters of the IFNCPA scheme: the encoding latency coefficient $γ$ , the upper limit of encoding latency $W_{\max}$ , and the offset $T_{o}$ , for avoiding collisions of passive ACK messages. A basic evaluation of these results is then carried out by simulation on a linear network topology.

Encoding latency coefficient

As stated in section “Determining the appropriate encoding latency and time-outs,” the encoding latency must be set as appropriate to the load. Let us examine the encoding latency coefficient $γ$ . Let $P_{e}$ be the encoding ratio, which is the ratio of the number of times a data chunk is encoded to the number of relay nodes that there are between the source node and the destination node, and let the target value of $P_{e}$ be 80%. Here, it is assumed that the message arrival interval in any single flow direction, say $p \to n$ , follows an exponential distribution with $1 / λ$ as the average. Using its probability distribution function distribution function $F (t) = 1 - \exp (- λ t)$ $(t \geq 0)$ , if the encoding latency for the $p \to n$ message flow can be represented as $W^{p \to n} = δ S_{i}^{p \to n} \approx δ / λ$ , $P_{e}$ can be estimated with the following

P_{e} = F (\frac{δ}{λ}) = 1 - \exp (- δ)

(6)

When $P_{e} = 0.8$ , $δ \approx 1.6$ . If $W^{p \to n} \geq 1.6 S^{n \to p}$ , from this and equation (3), we have

γ V^{p \to n} \geq 0.6 S^{p \to n}

(7)

Using the probability density function $f (x) = λ \exp (- λ x)$ , the mean deviation $V^{p \to n}$ can be approximated by

V^{p \to n} = \int_{0}^{\infty} | \frac{t - 1}{λ} | f (t) dt = \frac{2}{e λ} \approx 0.74 S^{p \to n}

(8)

From equations (7) and (8), $γ \geq 0.81$ . In the simulation below, therefore, $γ$ is set to $1.0$ in order to satisfy this condition.

Maximum encoding latency

As described in section “Determining the appropriate encoding latency and time-outs,” it is essential to suppress the transmission delays because the encoding latency lengthens especially when the traffic load is low. The parameter established for this, maximum allowed value $W_{\max}$ for $W^{p \to n}$ , is examined here. Let us begin by considering how this would be applied in real-time voice and image communications.

In ITU-T G.114,²¹ it is recommended that a one-way delay of 400 ms should not be exceeded for general network planning. According to ITU-T G.1010,²² the delays of less than 150 ms are preferred and those of 400 ms are a limit for audio or video applications. Therefore, the end-to-end delay (allowed delay) was set at 150 ms hereafter.

Next, the application was considered in an interior environment. The width of the building was varied from several tens to several hundreds of meters, the transmission distance was varied from several tens to 100 m, and the maximum hop number end to end was set at 10. Accordingly, dividing the allowed delay by the maximum hop number, 15 ms was set to the maximum $W_{\max}$ for the encoding latency in this study.

Offset

As described in section “Basic idea to avoid passive ACK collisions,” the offset $T_{o}$ , a parameter for the avoidance of passive ACK collision, must be longer than the transmission delay $T_{tx}$ . Since transmission waits such as back-off delay, queuing delay, and channel busy should be taken into account, $T_{o}$ must be a certain amount greater than $T_{tx}$ . In this study, simulations were carried out using $T_{o} = k T_{tx} (k = 0, 1, 2, 3, 4)$ as the setting for $T_{o}$ .

A total of 11 nodes were created in this simulation, spaced at equal intervals, to obtain $10$ hops. The nodes at each end (namely, end node) were the sources. Data messages were generated using the same exponential distribution and propagated toward and past each other. The load was the sum of the amount of data generated during a unit of time. The parameters employed in this simulation are displayed in Table 1. A commercial simulator Scenargie 2.0 was employed for performing this simulation. IEEE 802.11g is used in this simulation.²³ The reason is that its MAC is based on CSMA/CA like IEEE 802.15.4 for sensor networks.

Table 1.

Simulation parameters for linear topology.

Item	Value/type
Simulator	Scenargie 2.0
MAC protocol	IEEE 802.11g
Number of nodes	11
Distance between nodes	50 m
Communication range	50 m
Data rate	12 Mbit/s
Data size	480 bytes
Upper limit of encoding latency $(W_{\max})$	15 ms
Encoding latency coefficient $(γ)$	1.0
Maximum number of (re)transmissions	3
Simulation time	100 s
Trials	100

MAC: medium access control.

The mean encoding ratio, $P_{e}$ , was the mean value for the percentile fraction of times a native data chunk was encoded at relay nodes as it propagated all the way to its destination node. More precisely, $P_{e} = (\sum_{i} n_{e} (i) / \sum_{i} n_{h} (i)) \times 100$ , where $n_{h} (i)$ denotes the total hop count of data chunk $i$ which arrives at its destination node from its source node, and $n_{e} (i)$ represents the number of times data chunk $i$ was encoded on the way. The higher the mean encoding ratio, the more efficient the communications realized. The collection ratio, $P_{c}$ , is the percentile fraction of all data chunks actually received by the destination nodes to those generated at the source nodes. More precisely, $P_{c} = (\sum_{i} n_{d} (i) / \sum_{j} n_{s} (j)) \times 100$ , where $n_{d} (i)$ denotes the number of data chunks received by one end node $i$ as a destination node and $n_{s} (i)$ denotes the number of data chunks generated by the other end node $j$ as a source node. The end-to-end delay, $T_{d}$ , for a data chunk reaching the destination nodes is the mean time after generation by the source nodes passing before receipt by the destination nodes. More precisely, $T_{d} = (\sum_{i} t_{d} (i) / \sum_{j} n_{d} (j))$ , where $t_{d} (i)$ denotes the time from when data chunk $i$ is generated by its source node to when it is received by its destination node.

Figure 10 shows how the mean encoding ratio varied with the load. There was almost no difference between $T_{o} = 0$ and $T_{o} = T_{tx}$ , but it is clear that the ratios at these $T_{o}$ values were lower than those at the three other values examined. Figure 11 shows how the collection ratio varied with the load. This ratio was lower at $T_{o} = 0$ and $T_{o} = T_{tx}$ than at the three other values; furthermore, the difference between $T_{o} = 0$ and $T_{o} = T_{tx}$ shrank as the load increased. There was little difference among $T_{o} = 2 T_{tx}$ , $T_{o} = 3 T_{tx}$ , and $T_{o} = 4 T_{tx}$ but the ratio increased with increasing $T_{o}$ . These results indicate that the offset is effective if it is set to at least twice the transmission delay.

Figure 10.

Mean encoding ratio when the encoding latency was varied.

Figure 11.

Collection ratio when the encoding latency was varied.

Figure 12 presents the end-to-end delay as it varied with the load. The delay was greater at $T_{o} = 0$ and $T_{o} = T_{tx}$ than at the three other values. This is probably because avoidance of the collision of passive ACK was not achieved, necessitating many retransmissions. There was little difference among $T_{o} = 2 T_{tx}$ , $T_{o} = 3 T_{tx}$ , and $T_{o} = 4 T_{tx}$ . The reason for this was probably that the transmission waits due to back-off delay, queuing delay, and channel busy were greater than twice the transmission delay.

Figure 12.

Delay when the encoding latency was varied.

From the results in Figures 10 –12, the offset was set to $4 T_{tx}$ in the following simulations, as this seemed to promise high collection ratios and low delays.

Basic evaluation of the bidirectional communication environment under symmetric loads

A basic evaluation of the bidirectional communication environment was carried out while the model was under symmetric loads. Table 1 presents the parameters for this simulation; also, $T_{o}$ was set to $4 T_{tx}$ . In addition to the IFNCPA scheme, the IFNC scheme only, without passive ACK, and unicast transmission employing ACK at the MAC level (unicast scheme) were evaluated. Under IFNC, the parameters were set to the same values as used in IFNCPA; the only difference was that there were no retransmissions because of passive ACK.

Figure 13 shows how the mean encoding ratio varied with load under both the IFNCPA scheme and the IFNC scheme. IFNC resulted in lower ratios than for IFNCPA; the reason for this was probably that there were no retransmissions of encoded packets due to passive ACK, whereas a greater number of encoded packets gave a greater likelihood of “losing” one due to collision. In addition, during low loads, the encoding latency under the IFNCPA scheme was reduced to less than the mean packet arrival interval using $W_{\max}$ , and, as shown, the mean encoding ratio was lowered as a result. It is also visible that at high loads, however, the mean encoding ratio gradually approached the target encoding ratio of 80%.

Figure 13.

Mean encoding ratio under symmetric loads.

Figure 14 depicts how the collection ratio changed with load. Since the IFNC scheme does not equip with retransmissions, it has lower collection ratios than the IFNCPA or unicast scheme. Comparing the IFNCPA and unicast schemes, it is clear that the former has a higher collection ratio even under high loads and thus is a superior scheme to unicast. This is because the IFNCPA can lessen the number of transmitted packets, thanks to NC, while realizing reliable transmission, thanks to the passive ACKs.

Figure 14.

Collection ratio under symmetric loads.

Figure 15 provides the results for delay versus load. The reason for the lower delays under the IFNC scheme than under IFNCPA is that the retransmissions due to the passive ACK feature in IFNCPA increase the delays. Comparing IFNCPA to unicast, IFNCPA again shows longer delays because of the encoding latency; these delays all remained under the allowed delay of 150 ms at all loads.

Figure 15.

Delay under symmetric loads.

These simulation results indicate that IFNCPA provides higher collection ratios than does IFNC or unicast, and its delays remain within the allowed delay; therefore, it is a more effective scheme in a bidirectional communication environment under symmetric loads.

Basic evaluation of a bidirectional communication environment under asymmetric loads

The previous section presented a simulation of operation under the IFNCPA scheme in a bidirectional communication environment under symmetric loads, which is an ideal environment for IFNCPA. However, it is also essential to examine whether this scheme remains effective in an environment under asymmetric loads. In this section, therefore, a basic evaluation of a bidirectional communication environment under asymmetric loads is performed. The ratio $ρ_{1} / ρ_{2}$ of the load $ρ_{1}$ from the source node at one end of the linear topology to the load $ρ_{2}$ from the source node at the other end is the degree of asymmetry, and this was varied in the simulation while maintaining the total load at 250 kbit/s. Note that traffic loads are symmetric when $ρ_{1} / ρ_{2} = 1$ . The IFNCPA scheme and unicast scheme were compared. The parameter values of the simulation were those given in Table 1, and $T_{o}$ was set at $4 T_{tx}$ .

Figure 16 is a graph of the mean encoding ratio with respect to load asymmetry under the IFNCPA scheme. These results show that a greater degree of asymmetry is associated with a greater mismatch in directions of traffic and lower mean encoding ratio.

Figure 16.

Mean encoding ratio under asymmetric loads.

Figure 17 shows how the collection ratio varied with load asymmetry. From these results, the high collection ratio under the unicast scheme is explained as follows: the greater the degree of asymmetry, the greater the mismatch in directions of traffic, and the lower the probability of collisions between packets flowing in opposite directions. Under the IFNCPA scheme, packet collisions were reduced by the diminished traffic thanks to IFNC, so those schemes always showed higher collection ratios than the unicast scheme.

Figure 17.

Collection ratio under asymmetric loads.

Figure 18 presents the variation in delay with load asymmetry. Under the IFNCPA scheme, the delay increased with degree of asymmetry. The maximum delay was over the allowed delay of 150 ms when the degree of asymmetry is over about 3.5. This was caused by resulting increased RTO, which was calculated according to equations (4) and (5), because the disproportionate amount of traffic leads to the larger RTO in the traffic flow of one direction. If the RTO is limited to reduce the end-to-end delay, there is a possibility that the encoding efficiency is lowered. Investigation on this will be left as a future study.

Figure 18.

Delay under asymmetric loads.

These simulation results demonstrated that IFNCPA provides a higher collection ratio than unicast at the cost of end-to-end delay. Therefore, IFNCPA is an effective scheme in a bidirectional communication environment under the condition that the degree of asymmetry is less than 3.5.

Evaluation of practical applications by simulation

As described in section “Introduction,” the proposed scheme was employed in a model of the disaster response system using a wireless sensor network as an example of a practical application. The role of a sensor in a system such as this is to become disconnected from the network due to fire; therefore, the system cannot be a single-sink wireless network but rather a multiple-sink wireless network²⁴ in order to be sufficiently robust.

In support of evacuation and rescue, it is essential to obtain information not only about the event itself but also about potential victims of disaster who have deliberately stayed in vulnerable locations or waited too long to flee.^25,26 Wireless sensor network–based evacuation and rescue systems must employ packet transmission protocols that ensure high efficiency and reliability of transmission between nodes and sink nodes of any information gathered and delivered. Therefore, as described in this section, a multi-sink wireless sensor network–based evacuation and rescue system for disaster warning in a building was designed, and simulations were carried out for scenarios modeling bidirectional communication in such a system.

Simulation settings

This simulation evaluated a scenario employing a total of 28 nodes, comprising 26 sensor nodes and 2 sink nodes, on a single floor of a building (see Figure 19). As a result, the topology was nonlinear in this section, unlike the previous section. The model was based on a large (100 m × 450 m) shopping center, Aeon Lake Town, in Saitama Prefecture, Japan. It was assumed that the exterior and interior walls were of identical materials and thicknesses. Two types of traffic were generated to realize multiple bidirectional communications. In the first, sink nodes at each end of the model generated data packets at intervals according to identical exponential distributions (Traffic 1). In the second, the sensor nodes indicated in the figure by black circles were employed as source nodes, transmitting data packets with the identical exponential distribution to the sink nodes at each end of the model (Traffic 2). The sensor nodes without black circles act as relay nodes. The IFNCPA and unicast schemes were evaluated.

Figure 19.

Floor structure and node placement.

A commercial simulator Scenargie 2.0 was also used for performing this simulation. The parameters for this simulation are as shown in Table 2. Optimized Link State Routing (OLSR)²⁷ was the routing protocol and indoor radio propagation model was COST231 Indoor. The equations below use $P_{r}$ (dBm) for the received power, $P_{t}$ (dBm) for the transmitted power, $G_{t}$ (dBi) for the transmitting antenna gain, $G_{r}$ (dBi) for the receiving antenna gain, and $L$ (dB) for the path losses

P_{r} = P_{t} + G_{t} + G_{r} - L

(9)

Table 2.

Simulation parameters for use-case.

Item	Value/type
Simulator	Scenargie 2.0
MAC protocol	IEEE 802.11g
Routing protocol	OLSR
Propagation model	COST231 Indoor
Number of nodes	28
Break point	65 m
Transmission loss of wall	10 dBm
Transmission power	0 dBm
Receive threshold	−82 dBm
Antenna gain	0 dBi
Data rate	12 Mbit/s
Data size	480 bytes
Upper limit of encoding latency $(W_{\max})$	15 ms
Encoding latency coefficient $(γ)$	1.0
Offset value	$4 T_{tx}$
Max. number of (re)transmissions	3
Simulation time	100 s
Trials	100

MAC: medium access control.

The path losses $L$ in the COST231 Indoor model were calculated using the path losses in the free space $L_{free}$ (dB) as follows

L_{free} = 32.4 + 20 \log_{10} d + 20 \log_{10} f

(10)

L = L_{free} + 200 \log_{10} (d - d_{bp}) + n L_{w}

(11)

where $d$ (km) is the transmission distance, $f$ (MHz) is the frequency, $d_{bp}$ (km) is the break point, $n$ is the number of walls, and $L_{w}$ (dB) is the path loss through one wall.

Results and observations

Figure 20 presents the mean encoding ratio as it varied with the load under the IFNCPA scheme. The IFNCPA (Sink, Sensor → Sink) results indicate the combination of Traffic 1 and Traffic 2 findings, and the IFNCPA (Sink → Sink) results indicate the Traffic 1 findings. The mean encoding ratio increases to only around 25%, even at high loads, in the IFNCPA (Sink, Sensor → Sink) results. This was probably due to the occurrence of single-hop transmissions in which the messages traveled directly from their source nodes to their destination nodes, never passing through relay nodes, and thus, never being encoded at all. The IFNCPA (Sink → Sink) results, in which transmission was only between sink nodes, show an increase in mean encoding ratio with an increase in loading, to about 64%.

Figure 20.

Mean encoding ratio: use-case.

Figure 21 shows the collection ratio versus load. The unicast (Sink, Sensor → Sink) results indicate combined Traffic 1 and Traffic 2 findings, and the unicast (Sink → Sink) results indicate just Traffic 1 findings. Comparing the IFNCPA and unicast findings, the IFNCPA scheme provided higher collection ratios, including at high loads. Under the unicast scheme, Traffic 1 showed lower collection ratios than the combination of Traffic 1 and Traffic 2. This was probably due to a higher mean number of hops during Traffic 1, resulting in a greater number of message collisions.

Figure 21.

Collection ratio: use-case.

The variations in delay with respect to load are provided in Figure 22. The delay increases slightly with the load. This was attributed to increases in the number of collisions of passive ACK packets when the load became too high, necessitating many retransmissions. Comparing the IFNCPA and unicast schemes, there are delays due to the encoding latency under IFNCPA, so it showed longer delays than did the unicast scheme, but both the schemes had delays remaining within the allowed delay of 150 ms except the IFNCPA (Sink → Sink). In the IFNCPA (Sink → Sink) results, the end-to-end delay is below the allowed delay of 150 ms with load up to 0.9 Mbit/s, but at and above a load of 0.9 Mbit/s, it is over 150 ms but still below 200 ms. Finally, comparing the combination of Traffic 1 and Traffic 2 with Traffic 1 alone, the latter had higher delays. This was probably due to the higher mean number of hops in Traffic 1 condition.

Figure 22.

Delay: use-case.

These simulation results indicated higher collection ratios under the IFNCPA scheme than under the unicast scheme, that is, IFNCPA scheme is more reliable than the unicast scheme. The IFNCPA scheme has delays within the allowed value under a certain traffic load about 0.9 Mbit/s even for Traffic 1. These results suggest that the IFNCPA scheme is effective in an environment where the load is not extremely high.

Conclusion and remarks

In this study, the message transfer protocol of a scheme referred to as IFNC with passive ACK (IFNCPA) was proposed for the objective of highly efficient and reliable message transmission in a bidirectional communication environment. A system was investigated that would determine the encoding latency, a control parameter in IFNCPA, in a dynamic fashion with reference to the message arrival interval while addressing the issue of passive ACK collision. Parameter tuning was carried out and the effectiveness of the IFNCPA scheme was confirmed in a basic evaluation using a simulation assuming a linear network topology. A more realistic model of a wireless sensor network for evacuation and rescue systems accommodating bidirectional communication was simulated as an example of a practical application, and the IFNCPA scheme was shown to be effective and to have delays within the allowed value under a certain traffic load.

Since NC generates encoded data message from a plurality of data messages, an encoding waiting time is required. Therefore, there is essentially a trade-off between the encoding ratio and the end-to-end delay. In fact, only throughput performance was investigated in the past studies on IFNC^12–17 mentioned in section “Introduction.”¹⁸ From our simulation results, IFNCPA is considered to be useful for applications that can tolerate about a few hundred milliseconds for the end-to-end delay. Note that although the end-to-end delay is still below the limit of 400 ms for audio or video applications,²² it exceeds the allowed value of 150 ms in the environment under asymmetric and high traffic load. This is because $W_{max}$ is set to the value of the allowed delay divided by the maximum hop number as explained in section “Maximum encoding latency.” This means that the influence of retransmission delay is not taken into account at all. In order to deal with this impact, it should be set somewhat smaller. More careful parameter tuning of $W_{max}$ is also one of the important future issues.

Future research should feature experiments with actual equipment for evaluation of this approach and address routing protocols for effectively incorporating the IFNCPA scheme in equipment.

Footnotes

Handling Editor: Stefano Avallone

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by JSPS KAKENHI grant nos 24500080, 15K00124, and 15K00125.

ORCID iD

Yumi Takaki

Tomio Kamada

Chikara Ohta

References

Takimoto

Miura

Matsumoto

et al . Development of distributed autonomous cooperative evacuation guidance system. Sociotech 2011; 8: 82–90 (in Japanese).

Gelenbe

. Large scale simulation for human evacuation and rescue. Comput Math Appl 2012; 64(12): 3869–3880.

IEEE Standard for Part 11: wireless LAN medium access control (MAC) and physical layer (PHY) specifications, March 2012, http://ieeexplore.ieee.org/document/6178212/

IEEE Standard for Part 15.4: wireless medium access control (MAC) and physical layer (PHY) specifications for low rate wireless personal area networks (LR-WPANS), September 2006, http://ieeexplore.ieee.org/document/1700009/

Kleinrick

Tobagi

. Packet switching in radio channels: part II—the hidden terminal problem in carrier sense multiple-access and busy-tone solution. IEEE T Commun 1975; 23(12): 1417–1433.

Ahlswede

Cai

SYR

et al . Network information flow. IEEE T Inform Theory 2000; 46(4): 1204–1216.

Matsuda

Noguchi

Takine

. Survey of network coding and its applications. IEICE T Commun 2011; E94-B(3): 698–717.

Librino

Renda

Santi

. Evaluating multi-hop beaconing forwarding strategies for IEEE 802.11p vehicular networks. In: Proceedings of the 2013 IEEE vehicular networking conference, Boston, MA, 16–18 December 2013, pp.1–38. New York: IEEE.

Toh

. Ad hoc mobile wireless networks. Upper Saddle River, NJ: Prentice Hall, 2002.

10.

Ando

Takaki

Ohta

et al . Performance evaluation of efficient reliable packet transfer protocol for wireless multihop bidirectional communication environment. IEICE Tech Rep 2014; 114(210): 49–54 (in Japanese).

11.

Ando

Takaki

Ohta

et al . A study on inter-flow network coding with passive ACK for efficient and reliable bidirectional communication: optimal waiting time for encoding and timing control for passive ACK. IEICE Tech Rep 2015; 115(172): 43–48 (in Japanese).

12.

Katti

Rahul

et al . XORs in the air: practical wireless network coding. IEEE/ACM T Network 2008; 16(3): 497–510.

13.

Zhang

Chen

Marsic

. MAC-layer proactive mixing for network coding in multi-hop wireless networks. Comput Netw 2010; 54: 196–207.

14.

Lui

JCS

Chiu

. DCAR: distributed coding-aware routing in wireless networks. IEEE T Mobile Comput 2010; 9(4): 596–608.

15.

Yan

Zhang

Zheng

et al . CORE: a coding-aware opportunistic routing mechanism for wireless mesh networks. IEEE Wirel Commun 2010; 17(3): 96–103.

16.

Nguyen

TMT

Pujolle

et al . DODEX+: a new network coding scheme for mesh networks in mobile cloud computing. In: Proceedings of the 2014 IFIP wireless days (WD), Rio de Janeiro, Brazil, 12–14 November 2014, pp.1–6. New York: IEEE.

17.

Shafieinejad

Motamedi

Hendessi

et al . INCP: practical wireless network coding for multiple unicast sessions. Wireless Pers Commun 2016; 91(2): 623–651.

18.

Kafaie

Chen

Ahmed

et al . FlexONC: joint cooperative forwarding and network coding with precise encoding conditions. IEEE T Veh Technol 2017; 66(8): 7262–7277.

19.

Sato

Aketa

Otsuki

et al . Implementation and evaluation of dualcast by extending IEEE802.11. IEICE Tech Rep 2015; 115(311): 47–52 (in Japanese).

20.

Jacobson

. Congestion avoidance and control. In: Proceedings of the symposium on communications architectures and protocols (SIGCOMM ’88), Stanford, CA, 16–18 August 1988, vol. 18, no. 4, pp.314–329. New York: ACM.

21.

ITU-T Recommendation G.114. One-way transmission time, March 2005, https://www.itu.int/rec/T-REC-G.114/en

22.

ITU-T Recommendation G.1010. End-user multimedia QoS categories, November 2001, http://www.itu.int/rec/T-REC-G.1010-200111-I

23.

http://www.spacetime-eng.com/

24.

Erman

Havinga

. Data dissemination of emergency messages in mobile multi-sink wireless sensor networks. In: Proceedings of the 9th IFIP ad hoc networking workshop, Juan-les-Pins, 23–25 June 2010. New York: IEEE.

25.

Yamashita

Soeda

Noda

et al . Approach to safety and secure evacuation with sensor data mining. J IEICE 2011; 94(4): 294–298 (in Japanese).

26.

Satoh

Takahashi

Yamada

et al . Study on emergent behaviors of crowded people in a station through an agent-based simulation model. IEICE Tech Rep 2009; 108(456): 81–86 (in Japanese).

27.

Clausen

Jacquet

. Optimized link state routing protocol (OLSR). IETF RFC 3626, October 2003, https://tools.ietf.org/html/rfc3626