Source-linked AI summary
EDAP: An Efficient Data-Gathering Protocol for Wireless Sensor Networks
Arash Nasiri Eghbali, Nastooh Taheri Javan, Mehdi Dehghan
TL;DR
Directed Diffusion does not guarantee nearby sources’ paths join, and each source floods exploratory data separately. EDAP uses a nearby virtual sink for early aggregation and multipath forwarding; simulations report 75% improvement in network lifetime versus DD.
Problem
In Directed Diffusion, nearby-source paths are not guaranteed to join, and each source separately floods exploratory data to establish a route.
Source: §1 · p. 2Method
EDAP gathers nearby sources’ data at a virtual sink and uses multipath routing between that node and the sink for load balancing.
Source: §1 · p. 2Results
75% improvement in network lifetime in comparison to directed diffusion is reported for EDAP.
Source: §7 · p. 10Takeaways & Limitations
The authors conclude that EDAP combines clustering and multipath routing to address their respective drawbacks while improving network lifetime in simulation.
Source: §7 · p. 10The component approaches have tradeoffs: on-demand clustering forwards all sources over one path, which may partition the network, while disjoint multipath routing prevents aggregation.
Source: §7 · p. 10
Abstract
from arXiv · showhide
Directed Diffusion (DD), uses mechanisms such as data aggregation and in-network processing to suppress the additional data overhead however there is no guarantee that paths from nearby sources join after a few hops. Also for path construction, each source floods a distinct exploratory data (ED) packet through the network which is not necessary for nearby sources. In this paper an efficient data-gathering protocol (EDAP) is proposed to address the problems of late-aggregation and distinct ED-flooding through using a virtual sink (VS) node nearby the sources which plays the role of sink node and broadcasts local interest messages and routed gathered data toward destination. Also in this protocol, multiple paths are constructed between virtual sink and the sink node which leads to load-balancing and increase in the life-time of the network nodes. Our routing protocol can produce more than one disjoint or braided path and spread the gathered data properly between constructed paths according to their length and remaining energy. Simulation results shows that in this way a significant amount of energy can be saved and the network lifetime will be increased considerably (up to 75% better than DD).
1 Introduction
Directed Diffusion can aggregate data, but nearby sources are not guaranteed to converge quickly and each source separately floods an exploratory-data packet. EDAP combines local clustering with multipath routing to address these overhead and load-balancing issues.
1 Introduction
- In DD, nearby-source paths are not guaranteed to join, and each source separately floods an exploratory-data packet to establish its route.The packet’s traversed path is reinforced by the sink for later transmissions.Source: §1 · p. 2
- EDAP places a virtual sink near sources to aggregate their data early and avoid separate exploratory-data broadcasts by sources in the same cluster.The virtual sink broadcasts local interest messages and forwards gathered data toward the destination.Source: §1 · p. 2
- DD’s tendency to select the shortest route can deplete its nodes and lead to network partitioning along depleted paths.The risk is intensified when a nearby route is selected after a path refresh.Source: §1 · p. 2
- EDAP uses multiple paths between the virtual sink and sink to spread forwarding load across network nodes.The paper proposes node-disjoint paths, while noting this choice reduces the number of paths and can leave nodes unused after a path-node failure until refresh.Source: §1 · p. 2
- Limited Forward Improvement selectively sends exploratory data toward nodes nearer the destination, reducing network-wide broadcasts and increasing the number of constructed paths.The paper presents it as an alternative to the network-wide exploratory-data flooding of two-phase-pull and the bidirectional-link assumption of one-phase-pull.Source: §1 · p. 2
2 On Demand Clustering Protocol
On-Demand Clustering Protocol gathers nearby sources’ data at a virtual sink, which then forwards aggregated data toward the sink. Its phases select and refresh the virtual sink, discover routes, and handle expiration.
2 On Demand Clustering Protocol
- A virtual sink acts as the cluster head, collecting nearby sources’ information, aggregating it, and forwarding it toward the sink.The protocol describes four phases: virtual-sink selection, route exploration, virtual-sink refresh, and expiration handling.Source: §2 · p. 3
Phase I: Virtual Sink Selection
- Phase I selects a node on the original source-to-sink path as virtual sink; simulations assume it is at most two hops from the source.The virtual sink uses limited flooding for interest messages, with TTL limiting the cluster’s size and associated overhead.Source: §2 · p. 3
- When sources are out of radio range, multiple virtual sinks may be selected; the node with the least timestamp is chosen as the final virtual sink.The passage says this selection flooding overhead grows linearly with the number of sources.Source: §2 · p. 3
Phase II: Route Discovery
- Within a cluster, Two-Phase-Pull constructs source-to-virtual-sink routes by having sources send local exploratory data that the virtual sink reinforces.The passage also describes One-Phase-Pull as an alternative that sends data along paths traversed by local interest messages.Source: §2 · p. 3
- To connect the virtual sink to the sink, the virtual sink floods exploratory data and the sink reinforces the traversed path.Source: §2 · p. 3
Phase III: Virtual Sink Refreshment / Phase IV: Virtual Sink Expiration
- After a refresh period, the virtual sink selects the neighbor reporting the most remaining energy; a new virtual sink that cannot find a sink path retries with another neighbor.A virtual sink expires if it receives no data for the expiration period or if its and all neighbors’ energy falls below the threshold; sources then send directly toward the sink.Source: §2 · p. 4
3 Multi-path Construction Methods
The section develops simple and proactive multi-path construction methods, then addresses their difficulty creating distinct paths. It also describes energy-aware forwarding across paths of different lengths and remaining energy.
Simple Multipath Routing Method
- Simple construction can disjoint paths by sending negative reinforcement when an old positive reinforcement arrives, or increase path count by forwarding that reinforcement along the prior path.The latter can produce paths that are not completely disjoint.Source: Simple Multipath Routing Method · p. 4
Disjoint Proactive Multi-Path Construction Method
- Proactive construction tags exploratory-data packets with MP_ID, allowing the sink to reinforce the first packet for each identifier and ignore duplicates.This is intended to ensure the constructed paths are disjoint.Source: Disjoint Proactive Multi-Path… · p. 4
Limited Forward Improvement Method
- The premier packet problem occurs when the first flooded packet traverses most nodes and prevents other exploratory packets from reaching the sink.Limited Forward Improvement selectively forwards exploratory packets to the first F nodes nearer the sink, and can create more disjoint paths while reducing flooding cost.Source: Limited Forward Improvement Method · p. 5
Braided Proactive Multi-Path Construction Method
- Braided proactive construction lets each node forward up to T duplicate packets with different MP_IDs, allowing paths to share nodes while keeping gradients path-specific.The method is used with LFI; forwarded exploratory packets increase linearly with T.Source: Braided Proactive Multi-Path… · p. 5
One and a Half phase Pull Directed Diffusion
- The proposed proactive methods are described as one-and-a-half-phase-pull: they do not require bidirectional connections and use LFI to make exploratory-packet overhead almost negligible compared with TPP.Source: One and a Half phase Pull Directed… · p. 5
Energy-efficiency and load-balancing
- Path selection weighs minimum path energy and path length, favoring shorter paths while their energy is higher and longer paths as their energy falls.When minimum energy falls below eth or length exceeds lth, the selection probability calculated by formulas (1) and (2) is multiplied by 0.1; simulations use α = 2 and β = 4.Source: Energy-efficiency and load-balancing · p. 6
- Periodic PATH_ALIVE messages refresh paths and report their minimum energy; the paper also describes spreading packets across paths to balance load and reduce dropped packets.The messages are the same as positive-reinforcement messages.Source: Energy-efficiency and load-balancing · p. 6
4 EDAP Data Gathering Protocol
On-demand clustering gathers nearby sources' data at a virtual sink, then uses multipath routing from that node to the original sink. This combines aggregation before forwarding with multiple paths between the virtual sink and sink.
4 EDAP Data Gathering Protocol
- Nearby sources send data to a virtual sink, which acts as a sink for the cluster and aggregates the data before forwarding it.Source: §4 · p. 6
- The virtual sink forwards gathered data toward the original sink over multiple paths to implement load balancing.Source: §4 · p. 6
- Although disjoint multipath construction prevents aggregation along its paths, EDAP aggregates the data at the virtual sink before sending it over those paths.Source: §4 · p. 6
5 Methodology and Simulation
The section introduces the simulation methodology and assumptions, and states that it presents simulation results for each proposed algorithm.
5.1 Methodology
The methodology compares ODCP and MDD separately with DD and specifies protocol, energy, and traffic settings. It also describes how routing metrics, multipath construction, and ODCP energy use are evaluated.
5.1 Methodology
- ODCP and MDD are each compared with the original DD algorithm.Source: §5.1 · p. 7
Protocol Version
- Simulations use the diffusion3 implementation of DD in ns-2 version 2.30 for a more realistic evaluation.Source: Protocol Version · p. 7
Energy Model
- The simulations use the IEEE 802.11 MAC layer, the PCM-CIA WLAN card energy model, and a fixed 200-meter transmission range.The model specifies 0.660 W for sending and 0.395 W for receiving.Source: Energy Model · p. 7
Load Model
- Traditional DD floods interest messages every 30 seconds and exploratory data every 50 seconds; simulations used rates of 1 packet per second for ODCP, 1 or 10 for MDD, and 0.5 for EDAP.The virtual-sink expiration period was assumed to be 60 or 120 seconds.Source: Load Model · p. 7
Overhead, Drop Percentage and Delay Computation
- Overhead is non-data packets per received data packet, delay uses ping timestamps, and drop percentage is dropped packets divided by packets sent.The DD–MDD overhead comparison counts non-data packets while the sink receives 100 data packets; the authors note this measurement may not be quite precise.Source: Overhead, Drop Percentage and Delay… · p. 7
Multi-Path Calculation and Evaluation
- Multipath construction is tested on a 10-by-10 grid with one source and one sink, across four node densities and at least five runs per protocol.The evaluation measures path count, shared nodes, and minimum, maximum, and mean path lengths.Source: Multi-Path Calculation and Evaluation · p. 7
Energy Calculations for ODCP
- ODCP energy efficiency is compared with DD using 50-joule initial node energy over 250 seconds, with mean node energy measured every 50 seconds.Source: Energy Calculations for ODCP · p. 7
5.2 Simulation Results
The simulations compare ODCP, MDD, and ODCP-MP; ODCP’s energy and connection-lifetime effects vary with source count and virtual-sink refresh settings.
Energy Efficiency
- ODCP uses less energy than DD, with its efficiency advantage increasing as source count or network size relative to cluster size grows.Average energy across all network nodes rises, while average energy among cluster nodes falls because of clustering overhead.Source: Energy Efficiency · p. 7
Connection Life-time
- With fewer than four sources, ODCP decreases connection lifetime; lifetime improves as source count grows.The simulations keep the virtual sink fixed and omit its refresh phase.Source: Connection Life-time · p. 7
- Shorter virtual-sink refresh periods increase connection lifetime significantly, but also increase routing overhead.After 200 seconds most sources are disconnected, yet at least one remains connected and the connection lasts until second 430.Source: Connection Life-time · p. 7
Drop Percentage
ODCP’s drop percentage, delay, and routing overhead differ from DD, with setup overhead and source count shaping the results.
Drop Percentage
- ODCP’s drop percentage rises during cluster setup but remains constant as source count increases, while DD’s drop percentage rises considerably.The comparison is associated with Figure 4.c.Source: Drop Percentage · pp. 7–8, Figure 4 · p. 8
Average Delay
- ODCP decreases delay by reducing contention from flooded exploratory data, although cluster setup and virtual-sink selection increase network response time.Source: Average Delay · p. 8
Routing Overhead
- ODCP reduces routing overhead compared with DD by omitting extra exploratory-data packets.Source: Routing Overhead · p. 8
5.2.2 Multipath Directed Diffusion (MDD) Simulation Results
The MDD simulations examine multipath construction and connection time, reporting more paths from the LFI-enhanced braided proactive approach and better connection lifetime than DD.
Multipath Construction
- Braided proactive multipath routing with LFI produces more paths than the other methods, and multipath path counts grow with network density.Source: Multipath Construction · pp. 8–9
Connection Time
- Proactive multipath routing performs much better than DD on connection lifetime, and MDD delivers packets at 10 packets per second where DD fails.The passage attributes the lifetime result to limited forwarding improvement reducing exploratory-data flooding overhead.Source: Connection Time · p. 9
Overhead Estimation
The results report reduced overhead, delay, and packet drops for multipath approaches, alongside an EDAP lifetime gain that depends on path count and the lifetime definition.
Overhead Estimation
- Proactive multipath routing significantly reduces routing-protocol overhead compared with DD, while LFI decreases DD overhead.Source: Overhead Estimation · p. 9
Delay Computation and Drop Percentage
- Multipath methods significantly reduce delay and improve drop percentage, with delay reduction attributed to omitting extra exploratory-data packets.Source: Delay Computation and Drop Percentage · p. 9
5.2.3 EDAP Simulation Results Energy consumption
- In EDAP’s four-source simulation, adding paths between the virtual sink and sink lowers average network-node energy but improves load balancing.Source: §5.2.3 · p. 9
Network Lifetime
- EDAP increases network lifetime by about 75%, defining lifetime as the period when at least 50% of network nodes are alive.Source: Network Lifetime · p. 9
6 Related Works
The related-work survey contrasts multipath routing and clustering approaches, highlighting the energy constraints and routing complexity specific to wireless sensor networks. It also compares energy usage and network lifetime across routing methods and path counts.
6 Related Works
- TORA maintains a destination-oriented DAG with significant maintenance overhead, while DSR extensions construct alternate paths using source routing and intermediate-node disjoint paths.Taheri Javan et al. (2009) use common omni-directional antennas to send data simultaneously over multiple zone-disjoint paths.Source: §6 · p. 9
- Wireless sensor networks make multipath routing complex because nodes have local network views and lack source or destination location information; MSDD was proposed for load balancing and energy efficiency.The survey notes that multipath overhead is usually negligible in ad-hoc networks with up to a few hundred nodes, where energy efficiency is less constrained.Source: §6 · p. 9
- Ganesan et al. (2001) define braided paths by excluding individual nodes on a primary DD path, while the authors distinguish their own definition and describe combining their multipath algorithms with Gear.Gear uses geographic information to direct interest packets and reduce flooding traffic.Source: §6 · p. 9
- Figure 6 compares DD and DPMR energy usage and network lifetime across path counts with six sources, and compares DPMR with improved DPMR lifetime.Source: Figure 6 · p. 9
- EDDD offers real-time and best-effort gradients for delay and load balancing, but the cited work does not discuss path quality or quantity; this paper also uses Braginsky and Estrin’s RFI idea.The survey associates the gradients with reducing end-to-end delay and improving energy efficiency, respectively.Source: §6 · p. 10
- LEACH uses probabilistic cluster-head selection and direct sink transmission, while TEEN, PEGASIS, and MECH modify data transmission, aggregation, or cluster-head routing.The survey notes that LEACH cluster heads are not evenly distributed and that MECH uses local-neighbor information to assign them.Source: §6 · p. 10
7 Conclusion
EDAP combines virtual-sink clustering with multipath routing to address exploratory-packet overhead, late aggregation, and load balancing. Simulations report up to 75% higher network lifetime than directed diffusion, while noting trade-offs and limits to the measured gains.
7 Conclusion
- EDAP places a virtual sink near sources to gather their information and forward it toward the sink, omitting separate exploratory-data packets and enabling earlier aggregation.Source: §7 · p. 10
- Routing overhead decreases by omitting extra source-flooded exploratory packets, but early-aggregation gains were not included in simulations; connection lifetime also depends on virtual-sink refresh periods.Source: §7 · p. 10
- The proposed proactive multipath method and Limited Forward improvement target load balancing and energy efficiency while reducing exploratory-data traffic and two-phase-pull overhead.The conclusion reports that multipath routing leads to longer connection lifetimes.Source: §7 · p. 10
- On-demand clustering funnels merged sources through one path, which may partition the network, while proactive disjoint paths prevent aggregation.Source: §7 · p. 10
- 75% improvement in network lifetime over directed diffusion is reported, but the virtual-sink node may die before other nodes and limit multipath lifetime gains.The authors add that load balancing can increase the lifetime of nodes near the sink, which they say usually die first in real-world applications.Source: §7 · p. 10