Flood and Contain: An Optimized Repeal-Based Flooding Algorithm for Wireless Ad Hoc and Sensor Networks
<p>Behavior of Flood and Contain (F&C) vs. other schemes.</p> "> Figure 2
<p>F&C operation. (<b>a</b>–<b>c</b>) Flooding stage; (<b>d</b>–<b>f</b>) Chasing stage.</p> "> Figure 3
<p>Signaling packets and route delay from node 10 to 299 nodes in the network. (<b>a</b>) Signaling packets; (<b>b</b>) Route delay. RQ: 150 ms, RP: 0 ms.</p> "> Figure 4
<p>Maximum area (solid line) where launching a chase flooding generates similar overhead compared with traditional flooding. (<b>a</b>) Disk shaped network; (<b>b</b>) Lens shaped network.</p> "> Figure 5
<p>Repeal-flooding boundary versus target node’s distance to the network’s center.</p> "> Figure 6
<p>Signaling packets from node 10 to each target node, considering different repeal-flooding boundary (FB) values. (<b>a</b>) Flooding Boundary = 11; (<b>b</b>) Flooding Boudary = 7.</p> "> Figure 7
<p>Estimating the repeal-flooding boundary.</p> "> Figure 8
<p>Repeal-flooding boundary (optimized vs. estimated). (<b>a</b>) After 2 resource searches; (<b>b</b>) after 5 resource searches.</p> "> Figure 9
<p>Comparison of F&C with different <span class="html-italic">d</span>. (<b>a</b>) Signaling overhead; (<b>b</b>) Resource discovery delay.</p> "> Figure 10
<p>F&C: Signaling packets for different repeal-flooding boundary values. (<b>a</b>) Using optmized repeal-flooding boundary; (<b>b</b>) After 2 resource discovery searches; (<b>c</b>) After 5 resource discovery searches; (<b>d</b>) After 10 resource discovery searches.</p> "> Figure 11
<p>F&C: Disk and irregular network shape. (<b>a</b>) Irregular Shape; (<b>b</b>) Disk Shape.</p> "> Figure 12
<p>F&C under non-ideal conditions. (<b>a</b>) Irregular network shape; (<b>b</b>) Mobility: After nodes moved during 1 min; (<b>c</b>) Mobility: After nodes moved during 10 min.</p> "> Figure 13
<p>Comparison of flooding contention protocols. (<b>a</b>) Signaling overhead; (<b>b</b>) Route discovery delay.</p> ">
Abstract
:1. Introduction
- F&C reduces the number of control messages over the whole network, thus saving energy and making the network more resistant to some Vampire Energy Depletion Attacks [8].
- F&C protocol establishes a repeal-flooding boundary that delimits if the flooding is worth attempting to stop, allowing each node to decide whether it should initiate a chase flooding independently.
- Experiments demonstrate that F&C achieves an optimized performance with as few as just one previous chase flooding, and its performance is relatively immune to variations in the network shape, node density, and mobility patterns.
- Considering all possible locations of the source and target nodes within the network, F&C generates up to 35 percent fewer signaling packets on average, compared with traditional flooding. Other repeal-based schemes might transmit even more signaling packets on average than traditional flooding.
- F&C maintains a lower than or equal delay, compared with other repeal-based schemes. That is, it behaves at least as good as them while reducing the delay when the target node is far from the source node in terms of hops.
2. Related Work
3. Flood and Contain (F&C)
Algorithm 1 F&C (S, N, D) |
/*S: source node*/ |
/*D: Resource node set*/ |
/*N: node*/ |
|
3.1. Distance
3.2. Escape
3.3. Delay
4. Repeal Flooding Boundary
4.1. Finding the Repeal-Flooding Boundary
4.1.1. Disk-Shaped Scenario
4.1.2. Lens-Shaped Scenario
4.1.3. Finding the Repeal-Flooding Boundary in Practice
5. Experiments and Results
5.1. Choosing the Speed of the Initial Flooding,
5.2. Estimating the Repeal-Flooding Boundary
5.3. Density, Mobility and Shape Concerns
5.4. F&C versus Other Repeal-Based Flooding Protocols
6. Conclusions
Author Contributions
Funding
Conflicts of Interest
Abbreviations
F&C | Flood and Contain |
IoT | Internet of Things |
ID | Identificator |
BRIS | Broadcast-Repealing-Initiated in Source |
BRID | Broadcast-Repealing-Initiated in Destination |
TTL | Time to Live |
RQ | Resource Request |
RP | Resource Reply |
MPR | Multipoint Relay |
OLSR | Optimized Link State Routing |
References
- Gubbi, J.; Buyya, R.; Marusic, S.; Palaniswami, M. Internet of Things (IoT): A Vision, Architectural Elements, and Future Directions. Future Gener. Comput. Syst. 2013, 29, 1645–1660. [Google Scholar] [CrossRef] [Green Version]
- Xin, H.M.; Yang, K. Routing Protocols Analysis for Internet of Things. In Proceedings of the 2nd International Conference on Information Science and Control Engineering (ICISCE), Shanghai, China, 24–26 April 2015; pp. 447–450. [Google Scholar]
- Meshkova, E.; Riihijärvi, J.; Petrova, M.; Mähönen, P. A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks. Comput. Netw. 2008, 52, 2097–2128. [Google Scholar] [CrossRef]
- Ni, S.; Tseng, Y.; Chen, Y.; Sheu, J. The Broadcast Storm Problem in a Mobile Ad Hoc Network. Wirel. Netw. 2002, 8, 153–167. [Google Scholar]
- Safwat, A.; Hassanein, H.S.; Mouftah, H.T. VBS Routing. In The Handbook of Ad Hoc Wireless Networks; Structured Proactive and Reactive Routing for Wireless Mobile Ad Hoc Networks; CRC Press LLC: Boca Raton, FL, USA, 2003; pp. 219–220. [Google Scholar]
- Vu, K.Q.; Nguyen, T.B.; Vi, H.N.; Dao, M.T.; Nguyen, D.H. Survey of Recent Routing Metrics and Protocols for Mobile Ad-Hoc Networks. J. Commun. 2019, 14, 110–120. [Google Scholar] [CrossRef]
- Lim, H.; Kim, C. Flooding in Wireless Ad Hoc Networks. Comput. Commun. 2001, 24, 353–363. [Google Scholar] [CrossRef]
- Nguyen, V.; Lin, P.; Hwang, R. Energy Depletion Attacks in Low Power Wireless Networks. IEEE Access 2019, 7, 51915–51932. [Google Scholar] [CrossRef]
- Gargano, L.; Hammar, M. Limiting flooding expenses in on-demand source-initiated protocols for mobile wireless networks. In Proceedings of the 18th International Parallel and Distributed Processing Symposium, Santa Fe, NM, USA, 26–30 April 2004. [Google Scholar]
- Chang, N.; Liu, M. Revisiting the TTL-based Controlled Flooding Search: Optimality and Randomization. In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, Philadelphia, PA, USA, 26 September–1 October 2004; pp. 85–99. [Google Scholar]
- Zhang, H.; Jiang, Z. On reducing broadcast expenses in ad hoc route discovery. In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems Workshops, Columbus, OH, USA, 6–10 June 2005; pp. 946–952. [Google Scholar]
- Park, I.; Kim, J.; Pu, I. Blocking Expanding Ring Search Algorithm for Efficient Energy Consumption in Mobile Ad Hoc Networks. In Proceedings of the WONS 2006: Third Annual Conference on Wireless On-demand Network Systems and Services, Les Ménuires, France, 18–20 January 2006; pp. 191–195. [Google Scholar]
- Al-Rodhaan, M.; Mackenzie, L.; Ould-Khaoua, M. Efficient expanding ring search for MANETs. Int. J. Commun. Netw. Inf. Secur. 2010, 2, 169–177. [Google Scholar]
- Al-Rodhaan, M.A. Traffic Locality Oriented Route Discovery Algorithms for Mobile Ad Hoc Networks. Ph.D. Thesis, The Faculty of Information and Mathematical Sciences University of Glasgow, Glasgow, UK, 2009. [Google Scholar]
- Pu, I.M.; Shen, Y. Enhanced Blocking Expanding Ring Search in Mobile Ad Hoc Networks. In Proceedings of the 2009 3rd International Conference on New Technologies, Mobility and Security, Cairo, Egypt, 20–23 December 2009; pp. 1–5. [Google Scholar]
- Yassein, M.B.; Khamayseh, Y.M.; Al-Ameri, A.; Mardini, W.E. Routing Discovery Algorithm Using Parallel Chase Packet. Int. J. Adv. Comput. Sci. Appl. 2013, 4, 104–109. [Google Scholar]
- Pu, I.M.; Stamate, D.; Shen, Y. Improving time-efficiency in blocking expanding ring search for mobile ad hoc networks. J. Discret. Algorithms 2014, 24, 59–67. [Google Scholar] [CrossRef]
- Lima, R.; Baquero, C.; Miranda, H. Broadcast Cancellation in Search Mechanisms. In Proceedings of the 28th Annual ACM Symposium on Applied Computing, Coimbra, Portugal, 18–22 March 2013; pp. 548–553. [Google Scholar]
- Shintre, A.H.; Sondur, S. Improved Blocking Expanding Ring Search (I-BERS) protocol for energy efficient routing in MANET. In Proceedings of the International Conference on Recent Advances and Innovations in Engineering (ICRAIE-2014), Jaipur, India, 9–11 May 2014; pp. 1–6. [Google Scholar]
- Lima, R.; Baquero, C.; Miranda, H. Adaptive Broadcast Cancellation Query Mechanism for Unstructured Networks. In Proceedings of the 2015 9th International Conference on Next Generation Mobile Applications, Services and Technologies, Cambridge, UK, 9–11 September 2015; pp. 176–181. [Google Scholar]
- Hussain, S.Z.; Ahmad, N. Minimizing Broadcast Expenses in Clustered Ad-hoc Networks. J. King Saud Univ.-Comput. Inf. Sci. 2018, 30, 67–79. [Google Scholar] [CrossRef] [Green Version]
- Williams, B.; Camp, T. Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks. In Proceedings of the MobiHoc02: ACM Symposium on Mobile Ad Hoc Networking and Networking, Lausanne Switzerland, 9–11 June 2002; pp. 194–205. [Google Scholar]
- Jung, J.; Yookun, C.; Yeongkwun, K.; Injoo, K. ASTRAL: An Adaptive, Efficient, and Reliable Flooding Mechanism for MANET. In Proceedings of the 2010 ACM Symposium on Applied Computing, Sierre, Switzerland, 22–26 March 2010; pp. 731–732. [Google Scholar]
- Haas, Z.J.; Halpern, J.Y.; Li, L. Gossip-based Ad Hoc Routing. IEEE/ACM Trans. Netw. 2006, 14, 479–491. [Google Scholar] [CrossRef] [Green Version]
- Sasson, Y.; Cavin, D.; Schiper, A. Probabilistic Broadcast for Flooding in Wireless Mobile Ad Hoc Networks. In Proceedings of the 2003 IEEE Wireless Communications and Networking, New Orleans, LA, USA, 16–20 March 2003; pp. 1124–1130. [Google Scholar]
- Yassein, B.; Khaoua, O.; Papanastasiou, S. Performance Evaluation of Flooding in MANETs in the Presence of Multi-Broadcast Traffic. In Proceedings of the 11th International Conference on Parallel and Distributed Systems, Fukuoka, Japan, 20–22 July 2005; pp. 505–509. [Google Scholar]
- Zhang, Q.; Agrawal, D.P. Dynamic Probabilistic Broadcasting in MANETs. J. Parallel Distrib. Comput. 2005, 65, 220–233. [Google Scholar] [CrossRef]
- Mans, B.; Shrestha, N. Performance Evaluation of Approximation Algorithms for Multipoint Relay Selection. In Proceedings of the 3rd Annual Mediterranean Ad Hoc Networking Workshop, Bodrum, Turkey, 27–30 June 2004; pp. 1–14. [Google Scholar]
- Clausen, T.; Jacquet, P. Optimized Link State Routing Protocol (OLSR). RFC 3626, RFC Editor. 2003. Available online: https://tools.ietf.org/html/rfc3626 (accessed on 15 October 2020).
- Network Simulator v3. 2020. Available online: https://www.nsnam.org/ (accessed on 15 October 2020).
- Gomez, J.; Riggi, A. RegionDCF: A Self-Adapting CSMA/Round-Robin MAC for WLAN. Wirel. Pers. Commun. 2015, 85, 2169–2190. [Google Scholar] [CrossRef]
- Chu, W.; Ssu, K. Location-free Boundary Detection in Mobile Wireless Sensor Networks with a Distributed Approach. Comput. Netw. 2014, 70, 96–112. [Google Scholar] [CrossRef]
- Fayed, M.; Mouftah, H.T. Localised Alpha-shape Computations for Boundary Recognition in Sensor Networks. Hoc Netw. 2009, 7, 1259–1269. [Google Scholar] [CrossRef]
- Meurer, A.; Smith, C.P.; Paprocki, M.; Čertík, O.; Kirpichev, S.B.; Rocklin, M.; Kumar, A.; Ivanov, S.; Moore, J.K.; Singh, S.; et al. SymPy: Symbolic computing in Python. Peerj Comput. Sci. 2017, 3, e103. [Google Scholar] [CrossRef] [Green Version]
Algorithm | Technique | Contention Area | Flooding Speed | Chasing Technique |
---|---|---|---|---|
L-B [9] | BRIS | Unbounded | Different speeds | |
ERS [10] | No repletion | Bounded | No chasing | |
LHBA [11] | BRID | Bounded | Different speeds | |
BERS [12] | BRIS | Bounded | Stop and wait | |
BERS+ [13] | BRIS | Unbounded | Stop and wait | |
TLRDA-C [14] | BRIS | Unbounded | and , | Different speeds in/out the ring |
BERS* [15] | BRIS | Bounded | for | Stop and wait |
AODV-PC [16] | BRID | Unbounded | and , | Different speeds in/out the ring |
tBERS [17] | BRID | Bounded | Stop and wait | |
BCIR [18] | BRID | Bounded | Stop and wait | |
tBERS* [17] | BRID | Bounded | for | Stop and wait |
BCIR* [18] | BRID | Bounded | for | Stop and wait |
I-BERS [19] | BRIS | Bounded | Stop and wait | |
ABC [20] | BRID | Unbounded | Added delay | |
CMBERS+ [21] | BRID | Unbounded | for | Stop and wait |
Node | #RQ | #RP | R | r | |
---|---|---|---|---|---|
A | 6 | 8 | 7 | 1 | 5 |
B | 11 | 8 | 9 | 1 | 6 |
C | 0 | 3 | 2 | 2 | 1 |
D | 3 | 0 | 2 | 2 | 1 |
Node | #RQ | #RP | R | r | |
---|---|---|---|---|---|
A | 0 | 16 | 8 | 8 | 9 |
B | 16 | 0 | 8 | 8 | 9 |
C | 9 | 7 | 8 | 2 | 6 |
D | 6 | 10 | 8 | 2 | 6 |
Node | ||
---|---|---|
A | 9 | 9 |
B | 9 | 9 |
C | 6 | 6 |
D | 6 | 6 |
Parameter | Value |
---|---|
Nodes | 500 |
Sim area | 3100 × 3100 m |
Tx range | 250 m |
Positioning | Random |
Scenarios | 20 |
Ideal Condition | Non-Ideal Condition | ||
---|---|---|---|
shape | 65% (disk) | 72% (irregular) | |
density | 65% (uniform) | 61% (higher density) | 70% (lower density) |
mobility | 65% (static) | 60% (1 min) | 75% (10 min) |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Gomez, J.; Montes-de-Oca, M.; Camacho-Escoto, J.J. Flood and Contain: An Optimized Repeal-Based Flooding Algorithm for Wireless Ad Hoc and Sensor Networks. Sensors 2020, 20, 5914. https://doi.org/10.3390/s20205914
Gomez J, Montes-de-Oca M, Camacho-Escoto JJ. Flood and Contain: An Optimized Repeal-Based Flooding Algorithm for Wireless Ad Hoc and Sensor Networks. Sensors. 2020; 20(20):5914. https://doi.org/10.3390/s20205914
Chicago/Turabian StyleGomez, Javier, Martha Montes-de-Oca, and Jose Jaime Camacho-Escoto. 2020. "Flood and Contain: An Optimized Repeal-Based Flooding Algorithm for Wireless Ad Hoc and Sensor Networks" Sensors 20, no. 20: 5914. https://doi.org/10.3390/s20205914