To Code or Not to Code: When and How to Use Network Coding in Energy Harvesting Wireless Multi-hop Networks

I. INTRODUCTION

• COPE uses neighbor packet reports to choose packets for coding, combines them with XOR, and lets receivers recover packets using stored data.Nodes listen to transmitted packets and share information about packets held in memory.Source: §I · p. 1
• Existing network-coding implementations often prioritize coding gain at the expense of other performance aspects, motivating refined node decisions and an integrated framework.The paper notes that network coding can improve wireless-network efficiency; coding gain compares transmissions required with and without coding.Source: §I · pp. 1–2
• At coding nodes, To-Send-or-Not-to-Send uses optimal stopping to balance better coding opportunities against added transmission delay.Nodes learn when to transmit while selecting a coding pattern for the packet.Source: §I · p. 2
• At decoding nodes, To-Overhear-or-Not-to-Overhear learns whether to listen for packets that may improve neighboring coding or sleep to conserve energy.The approach models the sleep/wake trade-off with semi-Markov decision processes.Source: §I · p. 2
• The contributions include evaluating how the two decisions affect each other, improving overheard-packet usefulness assessment, and adapting the system model for concurrent operation.The paper presents the integrated framework for energy-harvesting wireless multi-hop networks.Source: §I · p. 2
• ENCODE combines the coding- and decoding-node decisions so nodes learn when and how to use network coding over time.The paper adapts the IEEE 802.11 MAC and harvesting-energy model, then compares the integrated framework with COPE and no network coding using four performance metrics.Source: §I · p. 2

A. COPE

• COPE uses opportunistic overhearing, coding, and neighbor-state learning to identify packet combinations that receivers can decode.Nodes listen promiscuously, retain packets, and report buffer contents to neighbors; coding nodes use those reports to choose combinations.Source: A. COPE · p. 3

B. Related Research on Decision-Making in Coding-Nodes

• Prior coding-node studies consider delaying packets for coding opportunities, but many focus on the restrictive Reverse Carpooling scenario.The reviewed approaches include Markov models, scheduling, and methods addressing delay, transmission cost, or energy-delay trade-offs.Source: B. Related Research on Decision-Making… · p. 3

C. Related Research on Decision-Making in Decoding-Nodes

• Prior decoding-node work reduces overhearing through packet filtering or sleep/wake scheduling, including integrated coding and scheduling approaches.The section also reviews feedback-based systems in which destination decoding decisions are communicated to sources.Source: C. Related Research on Decision-Making… · pp. 3–4

A. Preliminaries

• The two approaches address distinct trade-offs: coding gain versus end-to-end delay, and coding gain versus energy consumption.The second approach is modeled using semi-Markov Decision Processes and a reinforcement-learning solution.Source: §III · p. 4
• Separate implementations had promising results: the first improved throughput and energy consumption, while the second increased network lifetime versus COPE.These are results reported for the approaches separately, before their integrated implementation.Source: §III · p. 4

Motivation

• ENCODE uses one approach during packet transmission and the other during different periods, allowing nodes to learn when and how to use network coding.The integrated framework aims to combine the benefits of both approaches.Source: §III · p. 4

B. Motivation

• The example sequence shows n2 overhearing packet a, R delaying packet b, and R later sending coded packet a+b after receiving n2’s report.The sequence spans the four time slots ti, tj, tk, and tl.Source: §III · p. 4

Motivation

• When both approaches operate together, delayed or missed reception reports can leave a node unaware of a coding opportunity.The section identifies this interaction as a primary motivation for ENCODE.Source: §III · p. 5
• ENCODE values overheard packets using both their data and their reception reports, rather than data content alone.This change addresses the risk that a node disregards a report packet and misses a coding opportunity.Source: §III · p. 5

A. Network Model

• The model uses stationary, randomly distributed nodes in a graph of directed links, with neighbors defined by a communication radius.Nodes can act as traffic sources or destinations, and connections are half-duplex.Source: A. Network Model · p. 5
• Nodes use omnidirectional antennas and half-duplex operation, with separate queues for outgoing and overheard packets.Overheard packets remain in memory for a limited duration and are discarded by an aging algorithm.Source: A. Network Model · p. 5

B. Coding Model

• A coding node combines packets from different flows using XOR; a decoding node recovers its intended packet using stored packets.For an XOR of n original packets, the receiver needs n−1 of them to recover the expected packet.Source: B. Coding Model · pp. 5–6
• The paper uses XOR over GF(2), noting that larger Galois fields require more computation and can consume impractical energy on constrained devices.The described higher-cost operations include multiplication and Gaussian elimination.Source: B. Coding Model · p. 6
• Data packets carry reception reports, and a coding header identifies coded packets, reports, and acknowledgments.The reports convey packets stored by a neighboring node and the sender from which they were received.Source: B. Coding Model · p. 6
• A reception report records a packet source, its latest received packet identifier, and a bit sequence for recently received packets.The report can repeat reception information across multiple data packets.Source: B. Coding Model · p. 6

C. Energy model

• Nodes store harvested environmental energy in rechargeable batteries and turn off when their reserves are depleted.Energy-arrival timing is modeled as a stochastic process.Source: C. Energy model · p. 6
• Energy arrivals are stochastic, so harvesting and consumption rates need not match over time.The battery energy available at time t is denoted e_t.Source: C. Energy model · p. 6
• Transmission costs ET, reception or overhearing costs ER, and idle listening costs EI; sleep-mode consumption is assumed negligible.Source: C. Energy model · p. 6

D. MAC model

• The nodes use IEEE 802.11 with CSMA/CA; unicast acknowledgments support retransmission after a suspected collision.The study employs unicast mode for its reliability benefits.Source: D. MAC model · pp. 6–7
• Broadcast acknowledgments are disregarded, whereas unicast receivers acknowledge each packet.Source: D. MAC model · p. 6
• Transmission opportunities have exponentially distributed inter-arrival times, while packet arrivals and generation are modeled as Poisson processes.The packet-generation processes are assumed to be i.i.d.Source: D. MAC model · p. 7

• The framework first summarizes coding-node decisions, following the to-send-or-not-to-send approach.Source: §V · p. 7
• It then presents a revised to-overhear-or-not-to-overhear decision process for decoding nodes.Source: §V · p. 7
• The section concludes with modifications to IEEE 802.11 for implementing ENCODE.Source: §V · p. 7

• A coding node can transmit immediately to reduce delay or retain a packet while seeking a coding opportunity, though excessive delay may make it appear lost to upper layers.Source: A. Decision-making approach in coding… · p. 7
• The node’s state is the highest coding degree available in its queue, and each decision epoch offers waiting or transmitting as actions.Stages are intervals between consecutive transmission opportunities; transmitting moves the system to absorbing state d = 1, while waiting does not decrease d.Source: A. Decision-making approach in coding… · pp. 7–8
• Transmitting a packet of coding degree d saves d-1 transmissions, while waiting incurs a delay cost that discounts the coding benefit.The reward model uses exponential discounting to decrease reward monotonically with delay.Source: A. Decision-making approach in coding… · p. 8
• The 1-stage look-ahead rule compares the current reward with the expected reward from waiting one more stage to choose whether to transmit.The paper states that the rule is optimal under conditions established for this problem.Source: A. Decision-making approach in coding… · p. 8
• New packets and reception reports create coding opportunities; the model assumes Poisson arrivals and assigns each event a probability of increasing the best coding degree.Source: A. Decision-making approach in coding… · p. 8
• Higher coding-opportunity rates raise the transmission threshold, while rarer transmission opportunities lower it.Nodes therefore wait longer when coding opportunities are frequent and accept lower coding degrees when transmission chances are scarce.Source: A. Decision-making approach in coding… · p. 9

• ENCODE uses an SMDP to let nodes learn whether to sleep or remain awake for useful overhearing, rather than capturing all neighboring traffic indiscriminately.Overheard-packet value includes both data and reception reports, addressing an undesirable impact on coding-node decisions.Source: B. Decision-making approach in… · p. 9
• At each overhearing opportunity, a node chooses whether to sleep or stay awake, with state defined by remaining energy and nearby coding efficiency.Both state parameters are quantized into discrete values.Source: B. Decision-making approach in… · pp. 9–10
• The SMDP represents state transitions by action-dependent transition probabilities and expected time until the next decision epoch.Source: B. Decision-making approach in… · p. 10
• The reward links energy conservation to reduced transmission count, while sleeping instead of overhearing saves receiving energy under the stated radio-energy assumptions.Sleep-state energy is treated as negligible; environmental energy harvesting is modeled as a stochastic process with average rate ζ.Source: B. Decision-making approach in… · p. 10
• The model assigns two kinds of usefulness to overheard packets: packets that help neighbors code and reception reports that reveal coding opportunities.A report’s usefulness reflects the number of useful packets it identifies for coding.Source: B. Decision-making approach in… · pp. 10–11
• The solution modifies continuous-time Q-learning because an overheard packet’s reward may become known only later and can arrive out of sequence.The learning method adds a delay dimension to Q-values and retains action history to assign delayed rewards.Source: B. Decision-making approach in… · p. 11

• Coded packets use one constituent destination in the data-link destination field and list the remaining destinations in a coding header.A promiscuous receiver checks that header for its address and subsequent-hop status; only the primary destination acknowledges, and missing confirmation triggers retransmission.Source: C. Required changes in IEEE 802.11 · p. 11
• Local retransmissions resend a coded packet when any intended recipient fails to acknowledge, potentially with a new coding combination.Recipients that acknowledged the previous packet need not participate in the new combination.Source: C. Required changes in IEEE 802.11 · p. 12
• Asynchronous piggybacking attaches acknowledgments to data packets instead of sending separate immediate acknowledgments, reducing acknowledgment overhead.Source: C. Required changes in IEEE 802.11 · p. 12
• The numerical-results section compares ENCODE against COPE and a non-coding approach, but these passages provide no comparative outcome.Source: C. Required changes in IEEE 802.11 · p. 12

A. Simulation environment

• 200 stationary nodes were randomly deployed in a 1500-by-1500-meter area, with a nominal transmission range of 225 meters.Signal attenuation followed the Two-way ground model.Source: A. Simulation environment · p. 12
• In NS2 simulations, 200 stationary nodes were randomly deployed over a 1500 m × 1500 m area; nodes used modified IEEE 802.11 MAC and a simple geometric routing algorithm.Source: A. Simulation environment · p. 12
• Each flow connected two randomly selected nodes using UDP packets of 450 bytes, with exponentially distributed inter-packet intervals.The number of flows varied through random source-destination selection.Source: A. Simulation environment · p. 12
• The first decision approach used L = 22 packets and δ = 0.05; the second used β = 0.45, γ = 0.85, and θmax = 8.The state space was reduced by quantizing et to integers 1–8 and gt to 1–10; λd was estimated with an adaptive LMS filter of parameter 4.Source: A. Simulation environment · p. 12

1) Convergence of the RL solution

• The reinforcement-learning algorithm takes approximately 55,000 iterations to complete learning and achieve an optimal policy.The convergence plot is based on average rewards, and convergence time depends on runtime parameters.Source: B. Simulation Results · p. 12, Figure 3 · p. 13

2) Average coding gain

• As flow count rises, ENCODE’s average coding gain becomes slightly higher than COPE’s, while coding opportunities increase for both approaches.Fig. 4 compares ENCODE and COPE against no network coding.Source: Figure 4 · p. 13, B. Simulation Results · p. 13
• At 1000 Kbps average traffic, increasing node density creates more coding opportunities and improves coding gain.Fig. 5 depicts the impact of node density on coding gain.Source: Figure 5 · p. 13, B. Simulation Results · p. 13

3) Network throughput

• ENCODE demonstrates better throughput than COPE due to higher coding gain, while coding delays network saturation relative to no coding.The throughput comparison across the three approaches is shown in Fig. 6.Source: Figure 6 · p. 13, B. Simulation Results · p. 13
• With input traffic fixed at 1000 Kbps, network throughput increases slightly as node density rises.Fig. 7 illustrates throughput versus node density.Source: Figure 7 · p. 13, B. Simulation Results · p. 13

4) Average end-to-end delay

• At low traffic, delays are similar across the three methods; at higher traffic, coding adds slight delay that higher coding gain partly compensates.Fig. 8 compares end-to-end delay across the three approaches.Source: B. Simulation Results · pp. 13–14, Figure 8 · p. 14

5) Energy consumption

• Average energy consumption per delivered bit increases with traffic in all approaches, and ENCODE’s overhearing strategy aims to conserve energy compared with COPE.The comparison is shown in Fig. 9.Source: Figure 9 · p. 14, B. Simulation Results · p. 14

VII. Conclusion

• ENCODE integrates coding-node transmission timing via optimal stopping with decoding-node overhearing decisions learned through SMDP and reinforcement learning.The system model was redefined to evaluate how the two decision approaches affect each other.Source: B. Simulation Results · p. 14