pith. sign in

arxiv: 1907.05517 · v1 · pith:PWF7JIZKnew · submitted 2019-07-11 · 💻 cs.NI

The Gain of Energy Accumulation in Multi-hop Wireless Network Broadcast

Majid Khabbazian , Keyvan Gharouni Saffar This is my paper

Pith reviewed 2026-05-24 22:23 UTC · model grok-4.3

classification 💻 cs.NI
keywords energy accumulationwireless broadcastmulti-hop networkspath loss exponentenergy efficiency2D networksNP-hard problems
0
0 comments X

The pith

Energy accumulation in 2D wireless broadcast saves a constant amount of energy when the path loss exponent exceeds two and a logarithmic amount when it equals two.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper analyzes the energy savings obtained by allowing receivers to accumulate partial energy from multiple transmissions during broadcast in two-dimensional multi-hop wireless networks. Earlier results covered only linear networks; the authors extend the comparison to the plane, where both the minimum-energy broadcast problem with accumulation and without are NP-hard. They establish that the ratio of energies is bounded by a constant independent of network size when the path-loss exponent alpha is strictly larger than two, and grows as theta(log n) when alpha equals two. A reader would care because the result quantifies whether the extra mechanism of energy accumulation produces lasting gains as networks scale. The proofs compare optimal schedules under a deterministic path-loss model that treats received signal strengths as additive at each receiver.

Core claim

The central claim is that in two-dimensional multi-hop wireless networks the energy saving from broadcast with energy accumulation, relative to broadcast without accumulation, is constant when the path loss exponent alpha is strictly greater than two and is theta(log n) when alpha equals two, with n the number of nodes.

What carries the argument

The ratio of minimum total transmission energy required for broadcast when receivers accumulate energy from multiple senders versus when each transmission must be received in full from a single sender, under the deterministic path-loss model with fixed exponent alpha.

Load-bearing premise

The analysis assumes a deterministic path-loss model with fixed exponent alpha and perfect energy accumulation at receivers without interference, fading, or synchronization overhead.

What would settle it

Compute the ratio of minimum broadcast energies with and without accumulation in a large 2D point set with alpha equal to 2.5; if the ratio grows unbounded with the number of nodes the constant-saving claim fails.

Figures

Figures reproduced from arXiv: 1907.05517 by Keyvan Gharouni Saffar, Majid Khabbazian.

Figure 2
Figure 2. Figure 2: as an example. In [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 1
Figure 1. Figure 1: An m×m grid network with minimum node distance d, and n = m2 nodes. Analyzing the gain in general networks is challenging, because the analysis should work for any arbitrary arrangement of nodes in the network. To handle this, we first propose a novel conversion method that converts any given cooperative broadcast algorithm into a non-cooperative algorithm. Then, we leverage the conversion method to establ… view at source ↗
Figure 4
Figure 4. Figure 4: Finding transmitting nodes of non-cooperative broadcast algorithm. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Gtot versus n. Nodes are uniformly distributed in the network. We compared the algorithm by Caragiannis et al. [34] with the greedy filling algorithm under two other settings each with different node distributions. In one setting, nodes positions follow a Gaussian distribution with standard deviation of 0.5 around the center the disk. The result of this simulation is shown in Figures 6. 20 40 60 80 100 120… view at source ↗
Figure 6
Figure 6. Figure 6: Gtot versus n. Nodes have Gaussian distribution around center. In the second setting, for nodes distribution, we considered a clustered structure consisting of 5 cluster centers. Nodes locations around these centers follow a Gaussian distribution (σ = 0.5). The numerical results are shown in Figures 7. Next, we evaluated our conversion method explained in Section IV-C. When α = 2, this method converts any … view at source ↗
Figure 9
Figure 9. Figure 9: Gtot versus ln(n) for 2D grid networks. VI. CONCLUSION AND FUTURE WORK The cooperation gain is a measure of how much energy can be saved when energy accumulation is used in wireless broadcast. In this work, we analyzed the cooperation gain in 2D networks. We proved that when α > 2, the cooperation gain is constant irrespective of the network size and topology. When α = 2, we proved that the cooperation gai… view at source ↗
Figure 8
Figure 8. Figure 8: The conversion ratio when the greedy algorithm is used as the input [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 11
Figure 11. Figure 11: The shaded disk Dui is the biggest disk in I that intersects with Df (the disk with bold border). To sum up, node wi has received the message, wi <(n) f. It transmits with a power at least equal to (5rui ) α, and is at most 5rui away from f. Consequently, as in Case 1, f must have received the message from wi . APPENDIX B PROOF OF PROPOSITION 2 Let c 0 i denote the center of D0 ui . There is a node locate… view at source ↗
Figure 10
Figure 10. Figure 10: Disk Dui = Df (with bold border), and the disks in D that are not bigger than Dui and intersect with Dui . Asterisks represent the nodes in Si. To sum up, there is a node wi <(n) f that has received the message, and transmits with a power at least equal to (5rui ) α, and is at most 3rui away from f. Consequently f must have received the message from wi . 2) Case 2: Df 6∈ I: Since Df ∈ I / , there must be … view at source ↗
read the original abstract

Broadcast is a fundamental network operation, widely used in wireless networks to disseminate messages. The energy-efficiency of broadcast is important particularly when devices in the network are energy constrained. To improve the efficiency of broadcast, different approaches have been taken in the literature. One of these approaches is broadcast with energy accumulation. Through simulations, it has been shown in the literature that broadcast with energy accumulation can result in energy saving. The amount of this saving, however, has only been analyzed for linear multi-hop wireless networks. In this work, we extend this analysis to two-dimensional (2D) multi-hop networks. The analysis of saving in 2D networks is much more challenging than that in linear networks. It is because, unlike in linear networks, in 2D networks, finding minimum-energy broadcasts with or without energy accumulation are both NP-hard problems. Nevertheless, using a novel approach, we prove that this saving is constant when the path loss exponent alpha is strictly greater than two. Also, we prove that the saving is theta(log n) when alpha=2, where n denotes the number of nodes in the network.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript analyzes energy-efficient broadcast in 2D multi-hop wireless networks under the deterministic path-loss model. It claims to prove that the ratio of minimum broadcast energy without energy accumulation to the minimum with accumulation is bounded by a constant (independent of n) when the path-loss exponent α > 2, and is Θ(log n) when α = 2. Both the accumulation and non-accumulation broadcast problems are noted to be NP-hard; the authors assert that a novel approach yields the stated asymptotic bounds despite the hardness.

Significance. If the claimed bounds hold, the work supplies the first asymptotic characterization of the benefit of energy accumulation for broadcast in 2D networks, extending prior linear-network analyses. The explicit handling of NP-hard subproblems via a novel approach and the provision of parameter-free asymptotic statements constitute a clear theoretical contribution that could inform the design of energy-aware protocols.

minor comments (3)
  1. [Abstract] Abstract: the precise definition of 'saving' (whether it is the ratio of the two minima or an additive difference) is not stated; this should be made explicit in the first paragraph.
  2. [Introduction] The manuscript should include a short paragraph contrasting the 2D proof technique with the linear-network technique cited in the introduction, to clarify what is genuinely new.
  3. Notation for the minimum-energy broadcast problems (with and without accumulation) should be introduced once and used consistently; currently the same symbols appear to be overloaded in different sections.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive significance assessment, and recommendation of minor revision. No specific major comments were provided in the report, so we have no individual points requiring response or revision at this stage.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives asymptotic bounds on the ratio of minimum broadcast energies (with vs. without accumulation) for alpha > 2 (constant) and alpha = 2 (Theta(log n)) in 2D networks. These are presented as independent mathematical results obtained via a novel approach, with both problems acknowledged as NP-hard. No equations, parameters, or lemmas reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the model assumptions (deterministic path loss, perfect accumulation) define the setting rather than create internal circularity. The central claims remain externally falsifiable within the stated model.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard deterministic path-loss model and the definition of energy accumulation; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption Signal power decays as distance to the power -alpha
    Standard wireless propagation model invoked to define energy accumulation
  • domain assumption A receiver decodes once total accumulated energy exceeds a fixed threshold
    Core modeling choice for the technique whose gain is being bounded

pith-pipeline@v0.9.0 · 5726 in / 1262 out tokens · 23564 ms · 2026-05-24T22:23:06.073967+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    Ready or not, here comes the smart grid!

    S. Blumsack and A. Fernandez, “Ready or not, here comes the smart grid!” Energy, vol. 37, no. 1, pp. 61–68, 2012

    work page 2012

  2. [2]

    Security and privacy challenges in the smart grid,

    P. McDaniel and S. McLaughlin, “Security and privacy challenges in the smart grid,” IEEE Security and Privacy , vol. 7, no. 3, pp. 75–77, 2009

    work page 2009

  3. [3]

    From the internet of computers to the internet of things,

    F. Mattern and C. Floerkemeier, “From the internet of computers to the internet of things,” in From active data management to event-based systems and more , 2010, pp. 242–259

    work page 2010

  4. [4]

    The internet of things: A survey,

    L. Atzori, A. Iera, and G. Morabito, “The internet of things: A survey,” Computer networks, vol. 54, no. 15, pp. 2787–2805, 2010

    work page 2010

  5. [5]

    Machine-to-machine communications for home energy management system in smart grid,

    D. Niyato, L. Xiao, and P. Wang, “Machine-to-machine communications for home energy management system in smart grid,” IEEE Communi- cations Magazine, vol. 49, no. 4, pp. 53–59, 2011

    work page 2011

  6. [6]

    M2m: From mobile to embedded internet,

    G. Wu, S. Talwar, K. Johnsson, N. Himayat, and K. D. Johnson, “M2m: From mobile to embedded internet,” IEEE Communications Magazine , vol. 49, no. 4, pp. 36–43, 2011

    work page 2011

  7. [7]

    Cook and S

    D. Cook and S. Das, Smart environments: Technology, protocols and applications. John Wiley & Sons, 2004, vol. 43

    work page 2004

  8. [8]

    Poslad, Ubiquitous computing: smart devices, environments and interactions

    S. Poslad, Ubiquitous computing: smart devices, environments and interactions. John Wiley & Sons, 2011

    work page 2011

  9. [9]

    A sur- vey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks,

    A. A. Aziz, Y . A. Sekercioglu, P. Fitzpatrick, and M. Ivanovich, “A sur- vey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks,” IEEE communications surveys & tutorials , vol. 15, no. 1, pp. 121–144, 2013

    work page 2013

  10. [10]

    Local broadcast algorithms in wireless ad hoc networks: Reducing the number of transmissions,

    M. Khabbazian, I. F. Blake, and V . K. Bhargava, “Local broadcast algorithms in wireless ad hoc networks: Reducing the number of transmissions,” IEEE Transactions on Mobile Computing, vol. 11, no. 3, pp. 402–413, 2012

    work page 2012

  11. [11]

    Towards optimal broadcast in wireless networks,

    M. Nikolov and Z. J. Haas, “Towards optimal broadcast in wireless networks,” IEEE Transactions on Mobile Computing , vol. 14, no. 7, pp. 1530–1544, 2015

    work page 2015

  12. [12]

    Cooperative routing in wireless networks,

    A. Khandani, J. Abounadi, E. Modiano, and L. Zhang, “Cooperative routing in wireless networks,” in Allerton Conference on Communica- tions, Control and Computing , 2003

    work page 2003

  13. [13]

    Performance of fountain codes in collaborative relay networks,

    A. F. Molisch, N. Mehta, J. Yedidia, and J. Zhang, “Performance of fountain codes in collaborative relay networks,” IEEE Transactions on Wireless communications, vol. 6, no. 11, pp. 4108–4119, 2007

    work page 2007

  14. [14]

    Cooperative multihop broadcast for wireless networks,

    I. Maric and R. D. Yates, “Cooperative multihop broadcast for wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 6, pp. 1080–1088, 2004

    work page 2004

  15. [15]

    Delay constrained minimum energy broadcast in cooperative wireless networks,

    M. Baghaie and B. Krishnamachari, “Delay constrained minimum energy broadcast in cooperative wireless networks,” inIEEE INFOCOM, 2011, pp. 864–872

    work page 2011

  16. [16]

    Routing in cooperative wireless networks with mutual-information accumulation,

    S. C. Draper, L. Liu, A. F. Molisch, and J. Yedidia, “Routing in cooperative wireless networks with mutual-information accumulation,” in IEEE International Conference on Communications (ICC) , 2008

    work page 2008

  17. [17]

    Energy-efficient cooperative broadcast in fading wireless networks,

    C. Qiu, H. Shen, and L. Yu, “Energy-efficient cooperative broadcast in fading wireless networks,” in IEEE INFOCOM, 2014, pp. 1114–1122

    work page 2014

  18. [18]

    On minimum-energy broadcasting in all- wireless networks,

    F. Li and L. Nikolaidis, “On minimum-energy broadcasting in all- wireless networks,” in Local Computer Networks , 2001, pp. 193–202

    work page 2001

  19. [19]

    Minimum-energy broadcast in all-wireless networks: Np-completeness and distribution issues,

    M. ˇCagalj, J.-P. Hubaux, and C. Enz, “Minimum-energy broadcast in all-wireless networks: Np-completeness and distribution issues,” in International conference on Mobile computing and networking , 2002, pp. 172–182

    work page 2002

  20. [20]

    On the power efficiency of cooperative broadcast in dense wireless networks,

    B. Sirkeci-Mergen and A. Scaglione, “On the power efficiency of cooperative broadcast in dense wireless networks,” IEEE Journal on Selected Areas in Communications , vol. 25, no. 2, pp. 497–507, 2007

    work page 2007

  21. [21]

    Minimum energy accumulative routing in wireless networks,

    J. Chen, L. Jia, X. Liu, G. Noubir, and R. Sundaram, “Minimum energy accumulative routing in wireless networks,” in IEEE INFOCOM, 2005, pp. 1875–1886

    work page 2005

  22. [22]

    Routing in accumulative multi-hop networks,

    J. G ´omez-Vilardeb´o, “Routing in accumulative multi-hop networks,” IEEE/ACM Transactions on Networking, vol. 25, no. 5, pp. 2815–2828, 2017

    work page 2017

  23. [23]

    Efficient multi hop broadcast for wideband systems,

    I. Maricand and R. Yates, “Efficient multi hop broadcast for wideband systems,” in Allerton Conference on Communication, Control, and Computing, 2002

    work page 2002

  24. [24]

    Energy efficient broadcast in wireless ad hoc networks with hitch-hiking,

    M. Agarwal, L. Gao, J. H. Cho, and J. Wu, “Energy efficient broadcast in wireless ad hoc networks with hitch-hiking,” in IEEE INFOCOM , 2004, pp. 2096–2107

    work page 2004

  25. [25]

    Impact of cognition and cooperation on mac layer performance metrics, part I: Maximum stable throughput,

    A. A. Sharifi, F. Ashtiani, H. Keshavarz, and M. Nasiri-Kenari, “Impact of cognition and cooperation on mac layer performance metrics, part I: Maximum stable throughput,” IEEE Transactions on Wireless commu- nications, vol. 11, no. 12, pp. 4252–4263, 2012

    work page 2012

  26. [26]

    On the study of outage performance for cognitive relay networks (CRN) with the nth best-relay selection in Rayleigh-fading channels,

    X. Zhang, Z. Yan, Y . Gao, and W. Wang, “On the study of outage performance for cognitive relay networks (CRN) with the nth best-relay selection in Rayleigh-fading channels,” IEEE Wireless Communications Letters, vol. 2, no. 1, pp. 110–113, 2013

    work page 2013

  27. [27]

    Cognitive relay networks with energy and mutual-information accumulation,

    R. Atat, J. Ma, H. Chen, U. Lee, J. Ashdown, and L. Liu, “Cognitive relay networks with energy and mutual-information accumulation,” in IEEE INFOCOM Workshops, 2018. 16

    work page 2018

  28. [28]

    Energy-efficient broadcasting with co- operative transmissions in wireless sensor networks,

    Y .-W. Hong and A. Scaglione, “Energy-efficient broadcasting with co- operative transmissions in wireless sensor networks,” IEEE Transactions on Wireless communications, vol. 5, no. 10, pp. 2844–2855, 2006

    work page 2006

  29. [29]

    Asymptotic analysis of multi-stage cooperative broadcast in wireless networks,

    B. S. Mergen, A. Scaglione, and G. Mergen, “Asymptotic analysis of multi-stage cooperative broadcast in wireless networks,” IEEE/ACM Transactions on Networking , vol. 14, pp. 2531–2550, 2006

    work page 2006

  30. [30]

    On the con- struction of energy-efficient broadcast and multicast trees in wireless networks,

    J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “On the con- struction of energy-efficient broadcast and multicast trees in wireless networks,” in NFOCOM, 2000, pp. 585–594

    work page 2000

  31. [31]

    Localized minimum-energy broadcasting in ad-hoc networks,

    J. Cartigny, d. Simplot, and I. Stojmenovic, “Localized minimum-energy broadcasting in ad-hoc networks,” in IEEE INFOCOM, 2003, pp. 2210– 2217

    work page 2003

  32. [32]

    An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks,

    C. Amb ¨uhl, “An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks,” in ICALP, 2005, pp. 1139–1150

    work page 2005

  33. [33]

    Minimum-energy broadcast routing in static ad hoc wireless networks,

    P. Wan, G. C ˘alinescu, X. Li, and O. Frieder, “Minimum-energy broadcast routing in static ad hoc wireless networks,” in IEEE INFOCOM, 2001, pp. 1162–1171

    work page 2001

  34. [34]

    An exponential improvement on the MST heuristic for minimum energy broadcasting in ad hoc wireless networks,

    I. Caragiannis, M. Flammini, and L. Moscardelli, “An exponential improvement on the MST heuristic for minimum energy broadcasting in ad hoc wireless networks,” IEEE/ACM Transactions on Networking , vol. 21, no. 4, pp. 1322–1331, 2013

    work page 2013

  35. [35]

    Asymptotic gain analysis of cooperative broadcast in linear wireless networks,

    Z. Mobini and M. Khabbazian, “Asymptotic gain analysis of cooperative broadcast in linear wireless networks,” IEEE Transactions on Wireless Communications, vol. 15, no. 1, pp. 485–497, 2016

    work page 2016

  36. [36]

    Cooperative multicast for maximum network lifetime,

    I. Maric and R. Yates, “Cooperative multicast for maximum network lifetime,” IEEE Journal on Selected Areas in Communications , vol. 23, no. 1, pp. 127–135, 2005

    work page 2005

  37. [37]

    Goldsmith, Wireless Communications

    A. Goldsmith, Wireless Communications. Cambridge University Press, 2005

    work page 2005

  38. [38]

    T. S. Rappaport, Wireless communications - principles and practice . Prentice Hall, 1996

    work page 1996