A Search Strategy of Level-Based Flooding for the Internet of Things

Tie Qiu, Yanhong Ding, Feng Xia, Honglian Ma

In the sprawling world of the Internet of Things (IoT), finding a specific needle in a haystack of thousands of sensors is a surprisingly difficult task. Traditional methods either "scream" to the whole network (flooding) or "wander" aimlessly until they bump into the target (random walk). This paper introduces Level-Based Flooding (LBF), a strategy that maps the network into concentric rings to find targets faster and with significantly less energy.

TL;DR

Level-Based Flooding (LBF) is a novel search strategy for IoT networks that organizes nodes into "levels" based on their hop-distance from a central sink. By using these levels to set precise search limits and employing a smart neighbor-threshold for rebroadcasting, LBF cuts search costs and energy consumption by over 54% compared to traditional flooding.

What Problem Does This Paper Address?

The authors tackle the "Query Problem" in unstructured IoT networks. Imagine a sink node (the central controller) needs to find a specific sensor that just reported a temperature spike.

In an unstructured network, the sink doesn't know exactly where that node is. The standard solution is Basic Flooding: the sink sends a query to its neighbors, who send it to their neighbors, and so on. While fast, this creates a "broadcast storm"—a massive surge of redundant packets that drains the limited battery life of tiny IoT sensors. Alternatively, a Random Walk sends a single packet hopping from node to node, which saves energy but is agonizingly slow. The challenge is finding a middle ground: a search that is as fast as flooding but as efficient as a targeted strike.

Methods

The authors propose Level-Based Flooding (LBF), which operates in four distinct phases:

  1. Level Building Process (LBP): Upon deployment, the sink node broadcasts a one-time "level building" packet. As this packet moves through the network, every node calculates its "level"—the minimum number of hops it takes to reach the sink.
  2. Level Information Back (LIB): Nodes report their levels back to the sink. The sink now has a "map" of the network's depth, even if it doesn't know the nodes' physical coordinates.
  3. Searching Target Process (STP): When the sink needs to find a node, it sets the packet's Time-to-Live (TTL) exactly to that node's known level. This prevents the query from wandering into parts of the network further away than necessary.
  4. The "Smart" Rebroadcast: Instead of automatically forwarding every packet, a node waits a short moment (Random Assessment Delay). It counts how many of its neighbors have already processed the packet. If the percentage of "busy" neighbors exceeds a threshold ($P$), the node realizes the area is already covered and either drops the packet or sends it to just one neighbor instead of broadcasting.
  5. Sending Data Back (SDB): Once the target is found, it sends data back to the sink via a random walk that is restricted to nodes at lower levels. This ensures the data takes the shortest path back while varying the specific route to balance the energy load across different nodes.

Datasets

The researchers evaluated LBF using NS-2, a standard discrete event network simulator. Rather than using a static real-world dataset, they generated five synthetic simulation scenarios to test scalability:

  • Scenario 1: 50 nodes in a 250m x 250m area (High density).
  • Scenario 5: 4000 nodes in a 4000m x 4000m area (Low density).
  • Scenarios 2, 3, and 4 provided intermediate scales (125, 250, and 1000 nodes).

Key Insights and Ideas

  • Distance as a Filter: The most elegant "aha" moment is using the hop-count (level) to set the TTL. In basic flooding, packets often travel much further than the target, wasting energy. LBF effectively puts a "leash" on the search packet.
  • The Power of $P$: The rebroadcast threshold ($P$) is the secret sauce. In dense networks, you don't need every node to shout; a few well-placed broadcasts are enough. The paper shows that in high-density areas, you can set $P$ as low as 0.2 (20%) and still reach the target reliably.
  • Shortest Path via Random Walk: Usually, "random walk" implies a long, winding path. Here, by forcing the walk to only move to "lower level" neighbors, the authors guarantee a shortest-path return while preventing a single "best" path from being burned out by over-use.

Key Results

The simulations compared LBF against Basic Flooding across all five scenarios:

  • Cost & Energy: LBF reduced the average number of transmitted packets by 54.5% and total energy consumption by 54.4%.
  • Latency: LBF consistently found targets in fewer hops than basic flooding because it eliminated disordered paths.
  • Success Rate: Despite the aggressive pruning of redundant broadcasts, LBF maintained a successful query rate of nearly 100%, only slightly lower than basic flooding due to the potential for "dead" nodes in random deployments.
  • Scalability: As the network grew from 50 to 4000 nodes, the performance gap between LBF and basic flooding widened, proving LBF is better suited for large-scale IoT.

Limitations and Future Work

  • Static Networks: The current model assumes nodes don't move. In many IoT applications (like vehicular networks), levels would change constantly, requiring frequent, energy-expensive re-leveling.
  • Energy Hotspots: Nodes closer to the sink still consume energy faster because they handle more traffic—a classic "sink-hole" problem in sensor networks that LBF doesn't fully solve.
  • Empirical Thresholds: The optimal value for the threshold $P$ was determined through simulation (trial and error). The authors aim to develop a mathematical model to calculate the perfect $P$ automatically for any given network density.
  • Real-world Validation: The study is currently limited to the NS-2 simulator; testing on a physical "testbed" of hardware sensors is a noted next step.

Summary updated

Abstract

This paper deals with the query problem in the Internet of Things (IoT). Flooding is an important query strategy. However, original flooding is prone to cause heavy network loads. To address this problem, we propose a variant of flooding, called Level-Based Flooding (LBF). With LBF, the whole network is divided into several levels according to the distances (i.e., hops) between the sensor nodes and the sink node. The sink node knows the level information of each node. Query packets are broadcast in the network according to the levels of nodes. Upon receiving a query packet, sensor nodes decide how to process it according to the percentage of neighbors that have processed it. When the target node receives the query packet, it sends its data back to the sink node via random walk. We show by extensive simulations that the performance of LBF in terms of cost and latency is much better than that of original flooding, and LBF can be used in IoT of different scales.
BibTeX
@inproceedings{qiu2012search,
  author = {Tie Qiu and Yanhong Ding and Feng Xia and Honglian Ma},
  title = {{A Search Strategy of Level-Based Flooding for the Internet of Things}},
  booktitle = {Sensors},
  year = {2012},
  url = {https://openreview.net/forum?id=zAbNfxdD60},
}

Loading related content...

Figure