Optimal Message Bundling with Delay and Synchronization Constraints in Wireless Sensor Networks

Kyeong Soo Kim; Xintao Huan

arxiv: 1906.09039 · v1 · pith:XJZGL7TXnew · submitted 2019-06-21 · 💻 cs.NI · cs.PF

Optimal Message Bundling with Delay and Synchronization Constraints in Wireless Sensor Networks

Xintao Huan , Kyeong Soo Kim This is my paper

Pith reviewed 2026-05-25 18:25 UTC · model grok-4.3

classification 💻 cs.NI cs.PF

keywords message bundlingwireless sensor networksend-to-end delaytime synchronizationinteger linear programmingenergy efficiencydelay constraints

0 comments

The pith

An integer linear program finds node bundling numbers that minimize total transmissions while keeping end-to-end delay and synchronization accuracy within bounds.

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

Message bundling reduces energy use in wireless sensor networks but can increase delay and widen the gap between synchronization messages. The paper converts the dual requirements on delay and synchronization accuracy into an integer linear programming problem whose solution supplies a bundling number for every node. These numbers limit each link delay so their sum respects the end-to-end bound and keep synchronization messages frequent enough for the target accuracy. The resulting schedule uses the fewest transmissions possible under the constraints.

Core claim

By formulating joint maintenance of end-to-end delay and synchronization accuracy as an integer linear program, the method computes a set of optimal bundling numbers for the sensor nodes; these numbers constrain link-level delays and transmission intervals so that the network meets the user-specified delay bound and synchronization accuracy while the total number of message transmissions is minimized.

What carries the argument

Integer linear programming formulation that assigns bundling numbers to nodes to enforce linear constraints on per-link delays and message intervals.

If this is right

Total message transmissions drop while the delay bound and synchronization interval are still satisfied.
Each node receives a specific bundling number that directly caps its contribution to network delay.
The same linear constraints can be reused for any user-chosen delay threshold and synchronization accuracy target.
Energy consumption falls because fewer transmissions occur once the optimal numbers are applied.
The approach works for any synchronization scheme that includes synchronization messages inside the bundled packets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The ILP could be re-solved periodically if traffic patterns change, turning the static solution into an adaptive controller.
If queuing delays dominate, the model would need additional variables that capture contention rather than pure bundling effects.
The same translation from timing constraints into linear inequalities could apply to other resource-allocation problems such as duty-cycle scheduling.
Networks with heterogeneous node capabilities might require per-node bounds inside the same global program.

Load-bearing premise

End-to-end delay is exactly the sum of independent link delays set only by the bundling numbers, and synchronization accuracy depends only on the resulting transmission interval through linear constraints.

What would settle it

Deploy the computed bundling numbers in a testbed network and measure whether the observed end-to-end delays exceed the bound or synchronization errors grow when packet arrivals are correlated or queuing occurs.

Figures

Figures reproduced from arXiv: 1906.09039 by Kyeong Soo Kim, Xintao Huan.

**Figure 4.** Figure 4: E2E delay performance of the optimal bundling under static E2E [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗

**Figure 5.** Figure 5: E2E delay performance of the optimal bundling under dynamic E2E [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗

**Figure 6.** Figure 6: Number of message receptions and transmissions of sensor nodes with [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗

read the original abstract

Message bundling is an effective way to reduce the energy consumption for message transmissions in wireless sensor networks. However, bundling more messages could increase both end-to-end delay and message transmission interval; the former needs to be maintained within a certain value for time-sensitive applications like environmental monitoring, while the latter affects time synchronization accuracy when the bundling includes synchronization messages as well. Taking as an example a novel time synchronization scheme recently proposed for energy efficiency, we propose an optimal message bundling approach to reduce the message transmissions while maintaining the user-defined requirements on end-to-end delay and time synchronization accuracy. Through translating the objective of joint maintenance to an integer linear programming problem, we compute a set of optimal bundling numbers for the sensor nodes to constrain their link-level delays, thereby achieve and maintain the required end-to-end delay and synchronization accuracy while the message transmission is minimized.

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.

Desk Editor's Note private letter to a colleague

The paper casts message bundling as an ILP to hit joint delay and sync targets in WSNs, but the additive per-link delay model ignores wireless contention and is unlikely to hold in practice.

read the letter

The main move here is to take a recent energy-efficient synchronization scheme and add an ILP layer that chooses bundling numbers per node so total transmissions drop while end-to-end delay and synchronization accuracy stay inside user bounds. The formulation turns the requirements into linear inequalities on the bundling variables and hands the problem to a solver. That produces a concrete, computable answer instead of leaving the trade-off as a qualitative discussion, which is a useful engineering step for people who already have the base sync protocol running. The abstract is clear on the high-level mapping from bundling to link delay and interval, so the modeling intent is easy to follow. The soft spot is exactly the one the stress-test flags: the ILP treats each link delay as a deterministic function of its own bundling number and adds those delays along the path, with synchronization accuracy likewise a linear function of the resulting interval. In a real CSMA/CA or TDMA wireless setting the transmission time for any bundle also depends on back-off, collisions, and queue states at neighboring nodes, all of which are joint functions of the whole vector of bundling numbers. The ILP optimum can therefore be infeasible or suboptimal once the schedule hits the radio. The abstract supplies no derivation steps, no sensitivity analysis, and no validation data, so the size of the modeling error cannot be judged. This is aimed at researchers who build schedulers for battery-constrained sensor networks that also need timing guarantees. A reader who wants an off-the-shelf ILP template for bundling might borrow the constraint structure as a starting point. It deserves a serious referee if the full paper supplies either formal bounds on the approximation error or trace-driven simulations that compare the ILP output against measured packet latencies; without those checks the central claim rests on linearity assumptions that are known to be fragile in shared wireless media. I would send it for review rather than desk-reject, with a clear request for the validation material.

Referee Report

2 major / 1 minor

Summary. The paper claims that message bundling in WSNs can be optimized by translating joint constraints on end-to-end delay and synchronization accuracy (using a novel time synchronization scheme) into an ILP that computes per-node bundling numbers b_i to minimize transmissions while keeping delays and sync error within bounds.

Significance. If the modeling assumptions hold and the ILP produces feasible schedules, the work would provide a systematic optimization tool for energy-delay tradeoffs in time-sensitive WSN applications; the explicit reduction to ILP is a clear methodological strength when the linear constraints are justified.

major comments (2)

[ILP formulation and delay/synchronization modeling] The central ILP construction (described in the abstract and modeling sections) defines its feasible region via linear inequalities on bundling numbers that presuppose end-to-end delay equals the sum of independent per-link delays d_i(b_i) and that synchronization accuracy is a linear function of the resulting transmission interval. These assumptions are load-bearing: in CSMA/CA or TDMA wireless settings the actual transmission times depend on joint back-off, collision probability, and queue states across neighboring nodes, so the computed optimum may be infeasible on the real radio.
[Abstract and central construction] No derivation steps, validation data, or discussion of the modeling assumptions (additivity, independence, linearity) appear in the abstract; if the full manuscript similarly omits simulation or analytical justification that the ILP constraints remain valid under realistic MAC contention, the support for the claim that the ILP 'achieves and maintains' the requirements cannot be assessed.

minor comments (1)

The abstract would be clearer if it stated the exact form of the objective and the key linear constraints used in the ILP.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback highlighting the importance of clearly articulating the modeling assumptions underlying the ILP. We address the two major comments point-by-point below and will revise the manuscript accordingly to improve clarity on scope and applicability.

read point-by-point responses

Referee: [ILP formulation and delay/synchronization modeling] The central ILP construction (described in the abstract and modeling sections) defines its feasible region via linear inequalities on bundling numbers that presuppose end-to-end delay equals the sum of independent per-link delays d_i(b_i) and that synchronization accuracy is a linear function of the resulting transmission interval. These assumptions are load-bearing: in CSMA/CA or TDMA wireless settings the actual transmission times depend on joint back-off, collision probability, and queue states across neighboring nodes, so the computed optimum may be infeasible on the real radio.

Authors: The ILP is derived under the explicit modeling choice that per-link delays are additive and independent, and that synchronization error scales linearly with the resulting transmission interval; these are standard simplifications when the focus is on computing bundling numbers that meet end-to-end constraints within an analytical model. The assumptions hold when the underlying MAC permits predictable transmission times (e.g., scheduled TDMA or sufficiently low traffic that collisions are negligible). We agree that the manuscript should more explicitly delimit this scope. We will add a dedicated paragraph in the modeling section (and a brief reference in the abstract) stating the assumptions, the network conditions under which they are reasonable, and the fact that the optimality guarantee is with respect to the model rather than an arbitrary real radio. This revision will also note that extensions incorporating contention models are possible future work. revision: yes
Referee: [Abstract and central construction] No derivation steps, validation data, or discussion of the modeling assumptions (additivity, independence, linearity) appear in the abstract; if the full manuscript similarly omits simulation or analytical justification that the ILP constraints remain valid under realistic MAC contention, the support for the claim that the ILP 'achieves and maintains' the requirements cannot be assessed.

Authors: The abstract is a high-level summary; the derivation of the linear constraints from the delay and synchronization models is presented in the modeling sections of the full manuscript. We concur that the abstract and the paper would be strengthened by an explicit statement of the assumptions and their justification. We will revise the abstract to include a short clause noting the modeling assumptions and will expand the introduction/modeling section with a concise analytical justification for additivity and linearity under the considered traffic regime. If the current manuscript lacks simulation results under contended MAC protocols, we will add a limitations paragraph clarifying that the guarantees are model-based and that empirical validation on real radios remains future work. revision: yes

Circularity Check

0 steps flagged

No circularity; standard ILP formulation from stated constraints

full rationale

The paper translates delay and synchronization requirements into an ILP whose variables are bundling numbers and whose constraints are linear inequalities on per-link delays. No equations, fitted parameters, or self-citations are exhibited that reduce any claimed prediction or uniqueness result to the inputs by construction. The central step is a conventional optimization encoding of externally given bounds on end-to-end delay and transmission interval; the derivation therefore remains self-contained against the modeling assumptions supplied in the text.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The translation to ILP implicitly assumes linear additivity of delays and a direct functional dependence of synchronization accuracy on transmission interval.

axioms (2)

domain assumption End-to-end delay equals the sum of per-link delays determined by bundling numbers
Required for the ILP to enforce the global delay bound via local variables.
domain assumption Synchronization accuracy is a monotonic function of message transmission interval
Needed to express the accuracy requirement as a constraint on bundling.

pith-pipeline@v0.9.0 · 5674 in / 1331 out tokens · 25247 ms · 2026-05-25T18:25:08.755372+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages · 1 internal anchor

[1]

Data-aggregation techniques in sensor networks: A survey,

R. Rajagopalan and P. K. Varshney, “Data-aggregation techniques in sensor networks: A survey,” IEEE Communications Surveys Tutorials , vol. 8, no. 4, pp. 48–63, Fourth 2006

work page 2006
[2]

An optimized in-network aggregation scheme for data collection in periodic sensor networks,

J. M. Bahi, A. Makhoul, and M. Medlej, “An optimized in-network aggregation scheme for data collection in periodic sensor networks,” in Ad-hoc, Mobile, and Wireless Networks , 2012, pp. 153–166

work page 2012
[3]

Impact of network density on data aggregation in wireless sensor networks,

C. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann, “Impact of network density on data aggregation in wireless sensor networks,” in Proceedings of IEEE 22nd International Conference on Distributed Computing Systems, Jul. 2002, pp. 457–458

work page 2002
[4]

The design of an acquisitional query processor for sensor networks,

S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “The design of an acquisitional query processor for sensor networks,” in Proceedings of 2003 ACM SIGMOD International Conference on Management of Data, Jun. 2003, pp. 491–502

work page 2003
[5]

Energy-efﬁcient time synchro- nization based on asynchronous source clock frequency recovery and reverse two-way message exchanges in wireless sensor networks,

K. S. Kim, S. Lee, and E. G. Lim, “Energy-efﬁcient time synchro- nization based on asynchronous source clock frequency recovery and reverse two-way message exchanges in wireless sensor networks,” IEEE Transactions on Communications , vol. 65, no. 1, pp. 347–359, Jan. 2017

work page 2017
[6]

Survey on wireless sensor network devices,

M. A. M. Vieira, C. N. Coelho, D. C. da Silva, and J. M. da Mata, “Survey on wireless sensor network devices,” in Proceedings of 2003 IEEE Conference on Emerging Technologies and Factory Automation , Sep. 2003, pp. 537–544

work page 2003
[7]

On the Practical Implementation of Propagation Delay and Clock Skew Compensated High-Precision Time Synchronization Schemes with Resource-Constrained Sensor Nodes in Multi-Hop Wireless Sensor Networks

X. Huan and K. S. Kim, “On the Practical Implementation of Propagation Delay and Clock Skew Compensated High-Precision Time Synchronization Schemes with Resource-Constrained Sensor Nodes in Multi-Hop Wireless Sensor Networks,” arXiv e-prints , p. arXiv:1905.00554, 2019

work page internal anchor Pith review Pith/arXiv arXiv 1905
[8]

Energy-efﬁcient and rapid time synchronization for wireless sensor networks,

B. Kim, S. Hong, K. Hur, and D. Eom, “Energy-efﬁcient and rapid time synchronization for wireless sensor networks,” IEEE Transactions on Consumer Electronics , vol. 56, no. 4, pp. 2258–2266, Nov. 2010

work page 2010
[9]

CESP: A low-power high-accuracy time synchronization protocol,

F. Gong and M. L. Sichitiu, “CESP: A low-power high-accuracy time synchronization protocol,” IEEE Transactions on Vehicular Technology, vol. 65, no. 4, pp. 2387–2396, Apr. 2016

work page 2016
[10]

Exper- imental study for multi-layer parameter conﬁguration of WSN links,

S. Fu, Y . Zhang, Y . Jiang, C. Hu, C. Shih, and P. J. Marrón, “Exper- imental study for multi-layer parameter conﬁguration of WSN links,” in Proceedings of IEEE 35th International Conference on Distributed Computing Systems, Jun. 2015, pp. 369–378

work page 2015
[11]

TelosB datasheet,

“TelosB datasheet,” http://www.memsic.com/userﬁles/ﬁles/Datasheets/ WSN/telosb_datasheet.pdf, accessed: 30-04-2019

work page 2019

[1] [1]

Data-aggregation techniques in sensor networks: A survey,

R. Rajagopalan and P. K. Varshney, “Data-aggregation techniques in sensor networks: A survey,” IEEE Communications Surveys Tutorials , vol. 8, no. 4, pp. 48–63, Fourth 2006

work page 2006

[2] [2]

An optimized in-network aggregation scheme for data collection in periodic sensor networks,

J. M. Bahi, A. Makhoul, and M. Medlej, “An optimized in-network aggregation scheme for data collection in periodic sensor networks,” in Ad-hoc, Mobile, and Wireless Networks , 2012, pp. 153–166

work page 2012

[3] [3]

Impact of network density on data aggregation in wireless sensor networks,

C. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann, “Impact of network density on data aggregation in wireless sensor networks,” in Proceedings of IEEE 22nd International Conference on Distributed Computing Systems, Jul. 2002, pp. 457–458

work page 2002

[4] [4]

The design of an acquisitional query processor for sensor networks,

S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “The design of an acquisitional query processor for sensor networks,” in Proceedings of 2003 ACM SIGMOD International Conference on Management of Data, Jun. 2003, pp. 491–502

work page 2003

[5] [5]

Energy-efﬁcient time synchro- nization based on asynchronous source clock frequency recovery and reverse two-way message exchanges in wireless sensor networks,

K. S. Kim, S. Lee, and E. G. Lim, “Energy-efﬁcient time synchro- nization based on asynchronous source clock frequency recovery and reverse two-way message exchanges in wireless sensor networks,” IEEE Transactions on Communications , vol. 65, no. 1, pp. 347–359, Jan. 2017

work page 2017

[6] [6]

Survey on wireless sensor network devices,

M. A. M. Vieira, C. N. Coelho, D. C. da Silva, and J. M. da Mata, “Survey on wireless sensor network devices,” in Proceedings of 2003 IEEE Conference on Emerging Technologies and Factory Automation , Sep. 2003, pp. 537–544

work page 2003

[7] [7]

On the Practical Implementation of Propagation Delay and Clock Skew Compensated High-Precision Time Synchronization Schemes with Resource-Constrained Sensor Nodes in Multi-Hop Wireless Sensor Networks

X. Huan and K. S. Kim, “On the Practical Implementation of Propagation Delay and Clock Skew Compensated High-Precision Time Synchronization Schemes with Resource-Constrained Sensor Nodes in Multi-Hop Wireless Sensor Networks,” arXiv e-prints , p. arXiv:1905.00554, 2019

work page internal anchor Pith review Pith/arXiv arXiv 1905

[8] [8]

Energy-efﬁcient and rapid time synchronization for wireless sensor networks,

B. Kim, S. Hong, K. Hur, and D. Eom, “Energy-efﬁcient and rapid time synchronization for wireless sensor networks,” IEEE Transactions on Consumer Electronics , vol. 56, no. 4, pp. 2258–2266, Nov. 2010

work page 2010

[9] [9]

CESP: A low-power high-accuracy time synchronization protocol,

F. Gong and M. L. Sichitiu, “CESP: A low-power high-accuracy time synchronization protocol,” IEEE Transactions on Vehicular Technology, vol. 65, no. 4, pp. 2387–2396, Apr. 2016

work page 2016

[10] [10]

Exper- imental study for multi-layer parameter conﬁguration of WSN links,

S. Fu, Y . Zhang, Y . Jiang, C. Hu, C. Shih, and P. J. Marrón, “Exper- imental study for multi-layer parameter conﬁguration of WSN links,” in Proceedings of IEEE 35th International Conference on Distributed Computing Systems, Jun. 2015, pp. 369–378

work page 2015

[11] [11]

TelosB datasheet,

“TelosB datasheet,” http://www.memsic.com/userﬁles/ﬁles/Datasheets/ WSN/telosb_datasheet.pdf, accessed: 30-04-2019

work page 2019