CLOF: Contribution-level-based opportunistic flooding for multihop wireless networks

Abstract

In this study, we propose a contribution-level-based opportunistic flooding for multihop wireless networks. Traditional flooding techniques typically use fixed routing and predetermined relay nodes based on the assumption of fixed and reliable links. However, because of the inherent instability of wireless links, these approaches typically lead to fragile and unreliable broadcasting. To overcome this problem, we adopt an opportunistic routing where the relay node is determined by the transmission result. In addition, we introduce a new criterion: a contribution level defined as packet infectiousness, and it represents the transmission priority. Namely, contribution level implies the degree of contagiosity determined by the distribution of uninfected entities. It also falls with an increase in the number of infected entities. Thus, the contribution level of a node is initially determined by the number of neighbors and distances to the neighbors. Once a node receives a packet, it waits a certain amount of time according to the initial priority. The node changes its own contribution level when it overhears a packet while waiting. If the contribution level reaches near zero, it discards the received packet such that unnecessary duplicates are removed. Consequently, higher reliability and efficiency can be achieved.

Keywords

Multihop wireless networks broadcast flooding

Introduction

With the development of commercial cellular networks such as LTE, 5G, Mobile WiMAX, and WiBro Evolution, the studies on multihop wireless networks are no longer relevant and are not being conducted as frequently; therefore, these studies are disappearing fast. Currently, users can easily reach the commercial cellular networks since access networks for the commercial services are available anywhere a base station is installed. However, this does not mean that multihop wireless networks are no longer needed. For military purposes or maritime communications without infrastructure, multihop wireless networks are still valid.

Blind flooding is one of the representative broadcasting techniques for multihop wireless networks. Each node in a localized area retransmits every received packet once, without considerations for duplication. This is unproductive and causes “broadcast storm,” a network overload problem; therefore, the network bandwidth is wasted. For this reason, many studies^1–5 have focused on reducing the number of relay nodes. Such studies have built a minimized broadcast tree that covers all the network nodes based on the minimum connected dominating set (MCDS) problem. With this approach, the studies have been able to reduce the number of relay nodes but have selected the relay nodes in advance. However, the minimized broadcast tree is based on the assumption of fixed and reliable links; therefore, because of the instability in the real wireless medium, a node might fail to receive a broadcast packet.

Opportunistic routing^6–18,19 is a more effective alternative for exploiting the nature of broadcast medium. Opportunistic routing protocols do not specify the relay node before transmission. Instead, the metrically closest node to the destination attempts to forward data to the next node. Such studies have solved the efficiency and reliability problem simultaneously. These studies aim to utilize the nature of broadcast medium only for unicast and not even for broadcast.

In opportunistic routing, the two primary challenges are to determine (1) who relays the transmissions and (2) when the transmissions are relayed. Such challenges are generally resolved by priority-based forwarding with self-suppression based on overhearing. In the protocols, once a node receives a packet, before forwarding the packet, the node waits a certain amount of time based on the node’s priority and suppresses itself if it overhears an identical packet transmitted by another node. Therefore, the studies have secured the effectiveness and reliability of unicast routing rather than those of traditional routings.

In this study, we present a contribution-level-based opportunistic flooding that applies the aforementioned concept to broadcasts. The contribution level represents the infectiousness of a relay node; it varies with the number of neighbors and the distance to the neighbors. Thus, our proposed technique targets both broadcast effectiveness and reliability.

The rest of this article is organized as follows: section “Related works” discusses prior studies. Section “Motivation” describes our motivation behind this study. Section “Protocol design” introduces the design of the proposed protocol. Section “Simulation results” presents the results of the simulation and analyzes the results. Section “Conclusion” provides the conclusion and future work.

Related works

Previous studies on flooding have focused on the methods to reduce the number of transmissions. Lim and Kim’s¹ study proposed two flooding algorithms: self-pruning and dominant pruning. They showed how relay nodes can be determined in advance based on the MCDS problem as shown in Figure 1. In addition, scalable broadcast algorithm (SBA),² multipoint relaying (MPR),³ ad hoc broadcast protocol (AHBP),⁴ and connected dominating set (CDS)-based broadcast algorithms⁵ called “topology-based protocols”²⁰ have been used to conduct analyses based on graph theory. These methods oversimplify the problem, and thus they make two erroneous assumptions: first, relay nodes should be one-hop neighbors of the previous transmitter. However, sometimes a two-hop or a farther neighbor is better than a one-hop. Second, every link state would be unchanged and reliable. This is rather unstable and unpredictable, as shown in Figure 2. Furthermore, the link would be formed instantaneously, even at unexpectedly long distances. Under these inappropriate hypotheses, a trade-off between efficiency and reliability could not be overcome.

Figure 1.

Examples of topologies analyzed by the MCDS problem: (a) every node is red or is adjacent to a red node, and all the red nodes are connected and (b) every node is red or is adjacent to a red node, but all the red nodes are not connected. Thus, it is not a connected dominating set.

Figure 2.

Benefits of opportunistic transmission: (a) opportunistic transmission allows multiple links to act as one link and (b) opportunistic transmission can utilize fortunate increase in the transmission distance.

The opportunistic broadcast protocol (OppCast)²¹ spreads warning messages in a vehicular ad hoc networks (VANET) using opportunistic transmissions. The key challenge for the opportunistic problem is transmitting a reservation packet and a broadcast ACK (BACK). These kinds of packets exist within a specific time interval, and the transmitter can transmit packets without interference from any node. However, this can lead to performance degradation of the entire network because of a reduction in the spatial reuse. Opportunistic flooding proposed in Guo et al.²² is actually realized by multiple unicasts. Broadcast cannot be achieved since a packet is hardly received by at least two nodes in low-duty-cycle networks. Thus, its mechanism cannot guarantee the efficiency in always-awake networks.

Nevertheless, the minimum transmission-oriented opportunistic routings^7–13 and¹⁶ the explicit message exchange must be considered as performance degradation factors because the message can be lost, and this causes significant overhead. Thus, each study has shown an alternative coordination method. ExOR⁷ and MTS⁸ imposed strict timing constraints among forwarders to facilitate coordination during the relay process. MORE⁹ and DICE¹⁰ applied network coding to opportunistic routing in a clever way. Their critical weakness is their inability to prevent diverging paths. For this reason, simple opportunistic adaptive routing protocol (SOAR)¹¹ and Lee and Haas’ study¹² presented an ACK-based measure that can support multiple flows. SOAR’s main contribution involves forward node selection based on the default path and two types of ACKs such as per-hop ACK and end-to-end ACK. With this measure, diverging routes are prevented and duplicate transmissions are minimized. Moreover, it can efficiently support mutually crossed multiple flows. In the study by Lee and Haas,¹² only the destination of a flow can opportunistically receive the overheard packet. It makes the network easily discard duplicates and increase the entire throughput. social relation opportunistic routing (SROR)¹⁶ aims to extend the opportunistic routing concept with the social relation models between the mobile nodes such that the end-to-end packet delivery probability is maximized in the delay-tolerant mobile ad hoc networks.

The major drawbacks of the minimum transmission-oriented opportunistic routing schemes^7–13 are the imbalance in energy consumption and the security problem due to the large number of relays. Energy-Efficient Opportunistic Routing (EEOR)¹⁴ and Energy Saving via Opportunistic Routing (ENS-OR)¹⁷ emphasize the minimum energy consumption. To reduce the communication cost, EEOR¹⁴ chooses a relatively smaller amount of relay candidates than ExOR⁷ with the Bellman–Ford algorithm-based method. The ENS-OR algorithm¹⁷ calculates the optimal hop distance to achieve better network energy usage and longer network lifetime. Trust Minimum Cost Opportunistic Routing (TMCOR)¹⁵ prohibits malicious nodes to take part in the VANET, by judging them using the criteria: degree of trust.

Motivation

Trade-off between efficiency and reliability

Flooding techniques on broadcast trees¹ and some studies²⁰ have performed well only under the assumption that every link is reliable. However, if the transmission to a predetermined node fails, the packet cannot be delivered to the next because reliability in the real world cannot be guaranteed. Thus, the fewer relays are selected, the more easily the network reliability degrades. We define this problem as the reliability degradation problem.

In Figure 3(a), we consider the benefits of opportunistic transmission. Under the general broadcast-tree-based flooding, if source S fails to deliver a packet to intermediate 3, given that only node 3 is the predetermined relay, D cannot be reached. Thus, subsequent retransmissions do not proceed. However, if opportunistic transmission is employed, node 3’s role can be substituted with any of the other surrounding nodes. Therefore, we can resolve the reliability degradation problem by opportunistic transmission.

Figure 3.

Link states in erroneous assumption and real-world: (a) every link state is unchanged and reliable and (b) every link state is unstable and unpredictable.

Benefit of opportunistic transmission

In opportunistic transmission, the relay node is selected based on the transmission result. More opportunities are available for transmitting or receiving a packet. Considering the unstable and unforeseeable nature of the wireless medium, this technique can be more suitable for multihop wireless networks.

Figure 3(a) is a topology that well depicts one benefit of opportunistic transmission. Source S is connected to each intermediate node with a packet delivery ratio (PDR) of 0.1. Every intermediate node has a high PDR of 1 to the destination. Under traditional routing, source S must choose one of the intermediate nodes to deliver a packet to destination D, and only the selected intermediate node can participate in the routing. In this case, a packet would need to be transmitted 10 times on average to reach the next hop. However, under opportunistic routing, only 2.5 transmissions are required. This is because the probability of at least one intermediate node receiving the transmitted packet is $1 - (1 - 0.1)^{5} = 0.40951$ . Therefore, opportunistic routing can save 7.5 transmissions on average compared with traditional routing.

Another benefit of opportunistic transmission is the fortunate increase in the transmission distance from the source to relay node. A trade-off exists between the link quality and transmission progress. In Figure 3(b), source S is connected to destination D with three intermediate nodes in a row. If source S is under the traditional routing and intermediate node 2 has a proper PDR level, node 2 would be selected as the relay node. In this case, the transmission distance from node 2 is shorter than that from node 3. If node 1 were selected, source S would transmit a packet fewer times, but it would suffer a great loss in transmission distance. When node 3 is used as a relay node, more transmissions would be required because of a lower link quality, but the transmission distance from the source would be shorter than that of node 2. This means that the remaining distance from the relay node to D would be shorter than that for any other nodes, and thus the packet would reach destination D with a smaller number of packets.

To take advantage of the previously explained opportunistic transmission, one key challenge must be overcome: more than one node attempts to be the relay node, and thus unnecessary packets could be transmitted by these nodes. One method for resolving this issue is using “Receiver Coordination,” where only one node is selected as the relay node. The selected node informs the other nodes such that unnecessary packets are avoided. However, in this process, the information packet might be lost and can possibly cause illogical transmissions. Moreover, the larger the information packet becomes, the greater is the overhead on the network. Therefore, to avoid performance degradation, receiver coordination is applied for better robustness and zero overhead.

Challenges in opportunistic flooding

The goals of opportunistic flooding are to maximize the efficiency of each transmission and to not deteriorate network reliability while minimizing duplicate relays and incurring receiver coordination overhead. To achieve this goal, two important design issues must be resolved.

Coordination-free protocol

The explicit exchange of a coordination message is advantageous in that the channel state is allowed to be contention-free, and the transmission success of its message is guaranteed. However, the reservation area is unnecessarily wider than the actual transmission area. In addition, the transmission of the coordination message is another overhead to the network. Therefore, this could lead to throughput degradation and spatial reuse in the network.

Therefore, similar to previous research on opportunistic routings,^6–18 we execute coordination differently from an explicit message exchange. In other words, when a node receives a data packet, the node determines whether to retransmit according to the predetermined condition.

Transmission priority

The primary idea of the contribution level is as follows: each node’s transmission has a different influence on the network depending on the node’s distribution, that is, the more nodes with higher PDR are surrounding a node, the greater is the node’s influence. As shown in Figure 4, the influence of 15 nodes around the source is higher than the influence of eight nodes. In addition, even if each source has eight neighbors, the node closer to the nodes with higher PDR has a higher influence. Therefore, it is reasonable for the nodes with higher influence to retransmit the received packet.

Figure 4.

Contribution level determined by the number of neighbors and distances from the neighbors: the more nodes with higher PDR are surrounding a node, the greater is the node’s influence.

Contribution level is calculated based on the rule of blind flooding, in that each node retransmits the same packet only once. In Figure 5(a), the black nodes retransmit a packet. If all the links are reliable, the white node will receive the three identical packets. The probability that the received packet is valid is 1/3 because two out of the three received packets are duplicated. The number of valid packets is still one even if all the links were unreliable. The expected value of the received packet, however, is $a + b + c$ . Similarly, the probability that the received packet is valid is $1 / (a + b + c)$ . We shall refer to the number of nodes in the network as $N$ , the node that receives the packets as $r$ , all other nodes in the network as i, PDR from node $i$ to $j$ as $P_{ij}$ . Subsequently, the probability that the received packet is valid is shown in equation (1)

P r_{Valid} (Rx) = \frac{1}{\sum_{i = 1}^{N} p_{ir}}

(1)

Figure 5.

Probability that a received/transmitted packet is valid: (a) only one packet is valid among the packets the white node receives and (b) $a$ packet is valid among the packets the central black node receives.

As shown in Figure 5(b), the white node transmits a packet to the black node in the center. The probability that the transmitted packet is valid is strongly related to the probability that the received packet is valid. We simply multiply “a” by the probability of the received packet being valid because the PDR from the white node to the central black node is “a.” Thus, the probability that the transmitted packet is valid is $a / (a + b + c)$ . Similarly, let $t$ be the transmitter; subsequently, the probability that the transmitted packet is valid is defined in equation (2)

P r_{Valid} (Tx) = \frac{p_{tr}}{\sum_{i = 1}^{N} p_{ir}}

(2)

Moreover, the transmitted packet could be delivered to the other nodes and the white node in the center from the perspective of the entire network. Because the probability of the transmitted packet being valid can be defined as equation (2), the contribution level of node $t$ over the entire network $C_{t}$ is defined as

C_{t} = \sum_{t = 1}^{N} \frac{p_{tr}}{\sum_{i = 1}^{N} p_{ir}}

(3)

Protocol design

Assumptions

Pre-acquisition of the entire network’s information

One-hop or two-hop neighbor information is not sufficient for calculating the contribution level for the entire network. Every node in the network should have the entire link state information in advance such that each node can calculate the contribution level of the others and thus find its order of priority.

Use of the same transmission power

We assume that every node transmits a packet with the same transmission power. This is simply to solve the problem of when a node discards its retransmission. We do not consider the situation where a different network interface card (NIC) is used by each node. We set this aside as future work.

Relay node selection

All nodes in the network are relay candidates for the packet at the point where a packet is transmitted by a source. Unlike routing, whose source and destination are determined as one respective node, all nodes in the network are the destination, with the exception of the source. Thus, all nodes can always be the candidates for the relay of the packet they receive.

Priority timer-based forwarding

Contribution level is utilized as the primary metric for priority-based forwarding. When each node hears a transmitted packet, it first sets the timer depending on its own priority within the coverage. The ith forwarding node sets its forwarding timer to $(i - 1) \div n \times δ$ , where $i$ starts at one, $δ$ is 10 ms, and $n$ is the number of nodes. Subsequently, a node with a higher influence on the entire network forwards earlier among the nodes.

Self-stopping rule

Pruning

Deduplication is vital in flooding. The first constraint to deduplication transmission is pruning; if any two nodes are in a very close distance, their coverage are almost identical, as shown in Figure 6. As such, the succeeding forwarder has almost no influence to transmit the identical packet after the prior forwarder transmits the packet. We set $α$ to 0.95, and if a node hears the packet within a distance closer to $α$ , the packet is simply discarded. (The distance is expressed in the PDR metric here, not the physical distance.)

Figure 6.

Relationship between the distance and two nodes: if two nodes are sufficiently close to each other, the areas they can leverage are almost the same.

Reduction of contribution level

The second constraint to deduplicate transmission is as follows: in Figure 7, the size of the common area between the two circles is calculated with the distance between the two centers of the circle, expressed as $r^{2} (2 θ - 2 \sin θ)$ for circles of the same radius, and its ratio in the circle, $ρ_{θ}$ , is calculated as follows

ρ_{θ} = \frac{r^{2} (2 θ - 2 \sin θ)}{π r^{2}} = \frac{2 (θ - \sin θ)}{π}

(4)

where $π r^{2}$ is the area of a circle

\sin θ = \frac{\sqrt{r^{2} - d^{2} / 2^{2}}}{r}

(5)

θ = \sin^{- 1} \frac{\sqrt{r^{2} - d^{2} / 2^{2}}}{r}

(6)

Equations (5) and (6) are obtained from the Pythagorean theorem. By substituting equations (5) and (6) into the ratio, $ρ_{θ}$ can be converted into a function of $d$ , the distance between the two centers of the circle

ρ_{d} = \frac{2}{π} (\sin^{- 1} \frac{\sqrt{r^{2} - d^{2} / 2^{2}}}{r} - \frac{\sqrt{r^{2} - d^{2} / 2^{2}}}{r})

(7)

Figure 7.

Relationship between the distance and two nodes: the common area between the two circles is simply calculated with the distance between the two centers of the circle.

The relationship between the distance and portion of the intersection is plotted in Figure 8(a), and it partially approximates a linear equation. However, none of the nodes know their physical distance from each other because the location information is not available. Thus, we calculate the physical distance based on the Received Signal Strength Indicator (RSSI) as follows²³

P L_{d} = P L_{d 0} + 10 nlo g_{10} (\frac{d}{d 0}) + X_{σ}

(8)

γ_{d} = P_{t} + P L_{d} - P_{n}

(9)

PD R_{d} = {(1 - \frac{1}{2} ex p^{- \frac{γ_{d}}{2}})}^{8 f}

(10)

where $d$ is the transmitter–receiver distance, $n$ is the path-loss exponent (the rate at which the signal decays), and $X_{σ}$ is a zero-mean Gaussian RV (in decibels) with standard deviation $σ$ (multipath effect). Typically, $n$ and $σ$ are obtained through the curve fitting of empirical data.²⁴ In addition, we set the transmission power $P_{t}$ and noise floor $P_{n}$ to $- 80$ and $- 105 dBm$ , respectively.²⁵ The result of this substitution in equation (8) is shown in Figure 8(b). By substituting the inverse function of equation (9), the path-loss model formula,²⁶ into equation (10), a linear graph is obtained as an approximation, as shown in Figure 8(c). Therefore, we treat the ratio of the reduced contribution level as a linear equation in Figure 8(b) to simplify the calculation process.

Figure 8.

Relationship between distance, PDR, and contribution level: (a) relationship between the distance and portion of the intersection. It partially approximates a linear graph; (b) log-distance path-loss model can be converted to the relationship between the distance and PDR; (c) by substituting the inverse function of (b) into (a), the graph is obtained.

If a node hears the packet, it calculates the distance using the received signal strength and transmitted power. In addition, the node calculates the reduced contribution level using the simplified linear function shown in Figure 8(c). Moreover, the node either cancels its reserved transmission or discards the received packet when its contribution level reaches zero.

Simulation results

Evaluation method

We evaluate this protocol using NS-3 simulations. In this section, we use NS-3 simulations to compare the proposed protocol with traditional blind flooding with a random assessment delay (RAD)²⁰ and dominant pruning, of which the latter is a representative flooding technique based on fixed routing.

To measure the PDRs in the network, as required by this protocol, we send 1000 measurement packets. This process is performed as a warm-up period before the data packet is transmitted. To consider loss in a wireless medium, Yan’s error rate model is set to generate loss according to Bernoulli’s distribution.

Scenario

Our evaluation used the 802.11g protocol and the Request to Send/Clear to Send (RTS/CTS) was disabled to maintain fairness with the studies that use the default setting in most wireless networks. In addition, we disabled the auto-rate and set the data rate to 1 Mbps. We generated 1 Mbps of constant bit rate (CBR) traffic and used a 1000-byte packet size. We used a warming-up period to obtain and exchange the entire PDR metric and then measure the network performance with a 23-byte packet size in a 200 m × 200 m free space for 120 s. The 23-byte packet size is much larger than the size of the IEEE 802.11 beacon frame. However, it is the smallest size supported by the NS-3 simulator, and we consider that the neighbor information is contained within it.

We evaluate the efficiency of our protocols, incomplete and complete (denoted as “PF” and “CLOF,” which mean “blind flooding with priority-based forwarding” and “contribution-level-based opportunistic flooding,” respectively) and blind flooding (denoted as BF) using random-network topologies, and then evaluate their reliability using grid and random-grid network topologies.

Performance metric

We define three metrics for performance measurement, as follows:

Number of total transmissions. The number of transmissions performed by a protocol to spread an identical packet throughout the network.

Number of valid transmissions. The number of transmissions required until each node receives an identical packet at least once among the total transmissions.

Reliability. The percentage of nodes that receives the packet at least once among all nodes.

Efficiency evaluation

In random-network topologies, the number of nodes varies from 20 to 40. It is noteworthy that contention losses exist in addition to the aforementioned inherent wireless-link losses. This is also true for all other evaluations.

Figure 9 compares the numbers of valid and total transmissions of our protocols with blind flooding and dominant pruning. We consider each transmission to be valid if at least one node that receives the packet. Our expectation is that priority-based forwarding with only a contribution level can reduce the number of valid transmissions. Furthermore, self-stopping rules such as the pruning and reduction in contribution level reduce part of the duplicate transmission, and eventually, the total number of transmissions.

Figure 9.

Number of transmissions in a random-network topology: (a) priority-based forwarding with only a contribution level can reduce the number of valid transmissions; (b) self-stopping rules reduce part of a duplicate transmission, and the total number of transmissions; and (c) DP cannot achieve sufficiently high reliability unlike the others.

Figure 9 only shows the number of total and valid transmissions. Figure 10 shows the progress speed of each protocol in reaching the end of broadcasting with an increase in the number of relay nodes. A steeper slope indicates that the protocol can reduce the duplicates of relay nodes more and can cause more nodes to receive a packet with fewer transmissions. Provided that the slope is maintained steep, the protocol can use the network resource more efficiently.

Figure 10.

Transmission progress in random-network topology: a steeper slope indicates that the protocol can reduce the duplicates of relay nodes more and can cause more nodes to receive a packet with fewer transmissions. The more the number of nodes, the bigger is the CLOF gap. (a) Number of nodes: 20; (b) number of nodes: 30; and (c) number of nodes: 40.

Our protocol performs better for any number of nodes. The total number of transmissions for PF and BF is the same because our self-stopping rule is not applied. However, PF has a smaller number of valid transmissions. In other words, controlling the transmission order can easily spread a packet across the network effectively. Therefore, an adjustment in the self-stopping rule in our protocol reduces the total number of transmissions by 25%–55%, and the number of valid transmissions by 20%–45%. It is noteworthy that the number of valid transmissions is reduced by applying a self-stopping rule. We show the results of dominant pruning together for reference, but they are excluded from the comparison target because dominant pruning cannot achieve sufficiently high reliability unlike the others.

Reliability evaluation

In grid-network topologies, the grid width varies from five to seven cells. It is noteworthy that contention losses occur in addition to the inherent wireless-link losses. This is also true for all other evaluations.

Figure 11 compares the reliability and the percentage of the number of received nodes of our protocol with dominant pruning. Our expectation is that our protocol can overcome the reliability degradation problem with opportunistic transmission. Self-stopping rules, such as pruning and the reduction in the contribution level, reduce part of a duplicate transmission and eventually reduce the total number of transmissions. Dominant pruning cannot overcome the reliability degradation problem caused by low-link quality in a 5 × 5 grid. In a 6 × 6 grid with proper distance between nodes, we obtain the 70% performance. However, in a 7 × 7 grid, the performance degrades because of contention loss.

Figure 11.

Reliability in grid-network topology: CLOF overcomes the reliability degradation problem with opportunistic transmission, but dominant pruning cannot overcome the reliability degradation problem.

Our protocol performs better for any grid width. The reliability of each number of nodes is better than dominant pruning. Our protocol enhances the percentage of the number of received nodes by 25%–70%. In this experiment, we found that our protocol works similarly to blind flooding in sparse networks. We show the results of blind flooding together for reference, but the results are excluded from the comparison target because although blind flooding can achieve the highest reliability, it causes a significant network overhead problem.

Link state evaluation

Aside from the two evaluations, we verify that our protocol works properly without the assumption, “Pre-acquisition of the whole network information.” In this evaluation, only the one-hop and two-hop neighbor information can be obtained, such that the real-world situation is reflected better.

We evaluate our protocol (denoted as “two-hop” and “Global,” which mean “CLOF within two-hop link states from/to the close neighbor” and “CLOF with global link states,” respectively). In random-network topologies, the number of nodes varies from 20 to 40. Similar to the evaluations described in the previous sections, contention losses occur in addition to the aforementioned inherent wireless-link losses.

Figure 12 shows the comparison of the numbers of valid and total transmissions of our two protocols. We expect a large difference between their performances because none of the nodes in two-hop have sufficient information for an exact contribution level and global priority. CLOF with global link states performs better for any number of nodes. However, contrary to our expectation, the difference is not significant. CLOF with only two-hop link states performs well. This means that, although we ignore the near-zero PDRs that are far from a node, only the two-hop neighbor information can be sufficient in real network environments. In addition, we can reduce the overhead of the contribution level calculation for the entire network.

Figure 12.

Performance comparison in random topology with different link states: the performance difference is not significant, but CLOF with only two-hop link information performs as well.

Conclusion

Opportunistic flooding with a novel concept

In this study, we proposed a contribution-level-based opportunistic flooding technique that effectively realizes opportunistic broadcasting without exchanging any packet for coordination. We found that a node has a different influence on broadcasting based on its location. In addition, if some nodes are in a similar location, their influence is also nearly the same. The combination of these two insights allows our protocol to achieve higher efficiency and reliably in delivering a packet.

We found that the proposed protocol works similarly to blind flooding under the condition where the opportunistic transmission cannot be exploited. This is very similar to the aspect of opportunistic routing under such conditions. Therefore, we successfully applied the “opportunistic” concept to the flooding broadcast technique.

Future work

In real situations, almost all devices are equipped with various WNICs and use various transmission rates and powers. Potential areas for future work include reflecting situations closer to real world such as the transmission powers or other properties. Next, we could not match the total number of transmissions with the valid number of the current configurations, as indicated in the efficiency evaluation section. Therefore, we will study the protocol again and attempt to enhance it.

Owing to advanced cellular and access networks, studies on multihop wireless network are not performed as frequently. However, we believe that the potential still exists for environments without infrastructure. Under such environments, flooding is the only measure that maintains its topology. Therefore, we will aim to develop this study to suit to the mobile environment.

Footnotes

Acknowledgements

The basic version of this study has been published in an international conference, ICOIN 2015.

Handling Editor: Antonio Lazaro

Authors’ Note

Author Hyung-Yoon Seo is now affiliated to Department of Computer Software Engineering, Changshin University, Changwon, Republic of Korea.

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 the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (no. 2016R1A2B4013150).

ORCID iD

Seunggyu Byeon

References

Lim

Kim

. Flooding in wireless ad hoc networks. Comput Commun 2001; 24(3–4): 353–363.

Peng

X-C

. On the reduction of broadcast redundancy in mobile ad hoc networks. In: Proceedings of the 1st ACM international symposium on mobile ad hoc networking & computing, Boston, MA, 11 August 2000. New York: IEEE Press.

Qayyum

Viennot

Laouiti

. Multipoint relaying: an efficient technique for flooding in mobile wireless networks. INRIA, 2000, https://hal.inria.fr/inria-00072756/document

Peng

X-C

. AHBP: an efficient broadcast protocol for mobile ad hoc networks. J Comput Sci Technol 2001; 16(2): 114–125.

Peng

X-C

. Efficient broadcast in mobile ad hoc networks using connected dominating sets. J Software 2001; 12: 529–536.

Biswas

Morris

. Opportunistic routing in multi-hop wireless networks. ACM SIGCOMM Comp Com 2004; 34(1): 69–74.

Biswas

Morris

. ExOR: opportunistic multi-hop routing for wireless networks. ACM SIGCOMM Comp Com 2005; 35(4): 133–144.

Chen

Zhang

Z-L

. Optimal forwarder list selection in opportunistic routing. In: Proceedings of the IEEE 6th international conference on mobile adhoc and sensor systems, 2009 (MASS’09), Macau, China, 12–15 October 2009. New York: IEEE.

Zhang

. DICE: a game theoretic framework for wireless multipath network coding. In: Proceedings of the 9th ACM international symposium on mobile ad hoc networking and computing, Hong Kong, China, 26–30 May 2008. New York: ACM.

10.

Chachulski

Jennings

Katti

et al . Trading structure for randomness in wireless opportunistic routing. ACM SIGCOMM Comp Com 2007; 37(4): 169–180.

11.

Rozner

Seshadri

Mehta

et al . SOAR: simple opportunistic adaptive routing protocol for wireless mesh networks. IEEE T Mobile Comput 2009; 8(12): 1622–1635.

12.

Lee

Haas

. Simple, practical, and effective opportunistic routing for short-haul multi-hop wireless networks. IEEE T Wirel Commun 2011; 10(11): 3583–3588.

13.

Cacciapuoti

Caleffi

Paura

. A theoretical model for opportunistic routing in ad hoc networks. In: Proceedings of the international conference on ultra modern telecommunications & workshops, 2009 (ICUMT’09), St. Petersburg, Russia, 12–14 October 2009. New York: IEEE.

14.

Subramanian

Pandian

Gupta

. Energy efficient opportunistic routing in wireless sensor networks. Wirel Commun 2012; 4(7): 359–370.

15.

Zhizhong

Chuanhe

Liya

et al . A trusted opportunistic routing algorithm for VANET. In: Proceedings of the 2012 3rd international conference on networking and distributed computing (ICNDC), Hangzhou, China, 21–24 October 2012. New York: IEEE.

16.

Wong

GKW

Jia

. A novel socially-aware opportunistic routing algorithm in mobile social networks. In: Proceedings of the 2013 international conference on computing, networking and communications (ICNC), San Diego, CA, 28–31 January 2013. New York: IEEE.

17.

Luo

et al . Opportunistic routing algorithm for relay node selection in wireless sensor networks. IEEE T Ind Inform 2015; 11(1): 112–121.

18.

Triviño-Cabrera

Cañadas-Hurtado

. Survey on opportunistic routing in multihop wireless networks. Int J Comm Network Inform Secur 2011; 3(2): 170–177.

19.

Jadhav

Satao

. A survey on opportunistic routing protocols for wireless sensor networks. Procedia Comput Sci 2016; 79: 603–609.

20.

Williams

Camp

. Comparison of broadcasting techniques for mobile ad hoc networks. In: Proceedings of the 3rd ACM international symposium on mobile ad hoc networking & computing, Lausanne, 9–11 June 2002. New York: ACM.

21.

Lou

Zeng

. OppCast: opportunistic broadcast of warning messages in VANETS with unreliable links. In: Proceedings of the IEEE 6th international conference on mobile adhoc and sensor systems, 2009 (MASS’09), Macau, China, 12–15 October 2009. New York: IEEE.

22.

Guo

et al . Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links. IEEE T Comput 2014; 63(11): 2787–2802.

23.

Zuniga

Krishnamachari

. Link layer models for wireless sensor networks. USC, December 2005, pp.1–4, http://anrg.usc.edu/www/download_files/LinkModellingTutorial.pdf

24.

Sohrabi

Manriquez

Pottie

. Near ground wideband channel measurement in 800–1000 MHz. In: Proceedings of the 1999 IEEE 49th vehicular technology conference, Houston, TX, 16–20 May 1999, vol. 1. New York: IEEE.

25.

Rappaport

. Wireless communications: principles and practice, vol. 2. Upper Saddle River, NJ: Prentice Hall PTR, 1996.

26.

Zorzi

Rao

. Geographic random forwarding (GeRaF) for ad hoc and sensor networks: multihop performance. IEEE T Mobile Comput 2003; 2(4): 337–348.