Introduction
Wireless Mesh Networks (WMNs) increasingly rely on advanced routing techniques to meet growing throughput demands. Two prominent strategies are Inter-flow Network Coding (IRNC) and Opportunistic Routing (OR). IRNC allows relay nodes to combine packets from different flows (e.g., using XOR operations), reducing the number of required transmissions. OR, conversely, leverages the broadcast nature of wireless media by allowing any node in a "forwarding set" that receives a packet to forward it, thereby increasing reliability and throughput over traditional fixed-path routing.
However, integrating these two techniques is non-trivial. Most existing coding-aware routing schemes prioritize maximizing coding opportunities. This paper introduces HCOR (High-throughput Coding-aware Opportunistic Routing), which argues that maximizing coding can sometimes degrade performance if the "cost" of enabling that coding—often requiring a more restrictive forwarding set—outweighs the gains.
The Conflict Between Coding and Opportunistic Forwarding
The primary challenge in combining OR and IRNC lies in the decoding requirements. For a node to decode an XORed packet, it must have previously "overheard" the constituent native packets. To ensure this, a routing protocol might need to restrict the opportunistic forwarding set to only those nodes that have the necessary overheard information.
As shown in Figure 3, while node C might have an opportunity to code packets, doing so might force the use of a specific subset of forwarders (indicated by the colored ovals). If these forwarders have poor link quality compared to the full opportunistic set, the expected number of transmissions (ETX) may actually increase, negating the benefits of the network coding operation.
The HCOR Protocol Design
HCOR addresses this by treating network coding as a cost-benefit decision rather than an absolute goal. It utilizes a novel distributed routing scheme based on the following pillars:
1. Anypath Cost Metric
HCOR uses the Expected Transmission Count (ETX) to calculate the "anypath cost"—the total expected number of transmissions required to reach a destination through a specific set of forwarders. By comparing the anypath cost of sending native packets separately versus the cost of sending an encoded packet (potentially with a smaller, specialized forwarding set), HCOR only chooses to code when it results in a lower total cost.
2. Forwarding Set Selection
Nodes in HCOR dynamically manage their forwarding sets. A node identifies potential coding opportunities by tracking "Overheard Information" (OI) from its neighbors. This OI is piggybacked onto data packets, allowing nodes to discover coding possibilities multiple hops away.
In Figure 5, the protocol evaluates the paths through nodes like B and F. If coding at a specific node requires restricting the path to a less efficient route, HCOR's cost-based metric will favor standard opportunistic routing.
3. Dynamic Adaptation and Feedback
HCOR is designed for dynamic environments. It maintains a "Virtual Flow List" at each node. When a node successfully performs coding, it sends "coding feedback" (ACKs) upstream. This allows previous nodes in the path to update their local cost tables, effectively "steering" traffic toward nodes that currently offer high-value coding opportunities. If a flow stops, the coding gain automatically disappears from the calculation, and the network reverts to standard OR.
Performance Evaluation
The authors evaluated HCOR using the ns-2 simulator across various topologies, including Chain, X-topology, and 50-node random mesh networks.
- Throughput Gains: In standard Chain and X-topologies, HCOR achieved throughput improvements of 23% and 21%, respectively, over non-coding anypath routing.
- Comparison with COOR: When compared to COOR (Coding-Opportunity-aware Opportunistic Routing), which focuses solely on maximizing coding instances, HCOR showed a significant advantage. In random 50-node topologies, HCOR provided a throughput gain of over 25% compared to COOR.
- Bottleneck Handling: In "Diamond" and "Cellular" topologies designed to create bottlenecks, COOR often performed worse than non-coding routing because it forced coding at nodes with poor output links. HCOR correctly identified these as "expensive" coding opportunities and avoided them, maintaining superior performance.
Conclusion
HCOR demonstrates that in the context of opportunistic routing, the "price" of network coding must be carefully managed. By using a rigorous anypath cost metric, HCOR ensures that network coding is only applied when it provides a genuine throughput benefit. This adaptive, cost-aware approach makes HCOR a robust solution for high-performance wireless mesh networks, significantly outperforming protocols that blindly chase coding opportunities.
Summary updated