Abstract: Focused on the energy-efficiency optimization problem of broadcasting with minimum end-to-end delay constraint for asymmetric duty-cycled sensor network, a spatial-temporal state graph that represented the broadcasting spatial-temporal characteristics was first constructed, the target issue was modeled as the forwarding decision subset coverage problem, and then a Minimum-Cost forwarding decision Subset Coverage Algorithm (MC-SCA) and a Cost-Balanced forwarding decision Subset Coverage Algorithm (CB-SCA) were proposed. MC-SCA and CB-SCA both determined the optimal forwarding decision subset in an iterative way. MC-SCA greedily selected the forwarding decision with the least ratio of forwarding cost to the number of new covered nodes in each round of iteration, and CB-SCA greedily selected the forwarding decision which would bring less forward load and more new covered nodes in each round of iteration. In the comparison experiments with the typical Random Parent Node Selection Algorithm (RPNS-A), the total broadcasting energy consumption of MC-SCA decreases by 24.23% in average, and compared with RPNS-A, MC-SCA and the minimum-load-first greedy algorithm, the node maximum broadcasting load of CB-SCA respectively decreases by 48.69%, 65.21% and 10.64% in average, which implies that CB-SCA always achieves the better energy fairness of broadcasting.

Key words: Wireless Sensor Network (WSN), asymmetric duty-cycle, broadcast scheduling, energy efficiency, load balance

摘要： 针对非对称占空比传感网中最小端到端延迟约束下的广播能效优化问题，首先构造了一个能够刻画广播时空特征的时空状态图，将目标问题建模成转发行为子集覆盖问题，然后分别提出了一种面向总能耗优化的最小代价转发行为子集覆盖算法（MC-SCA）和一种面向能量公平性的代价均衡转发行为子集覆盖算法（CB-SCA）。MC-SCA和CB-SCA都是采用迭代的方式选择最优转发行为子集。MC-SCA在每一轮迭代中贪心地选择转发行为代价与新增覆盖节点数量的比值最小的转发行为，而CB-SCA在每一轮迭代中贪心地选择带来更小节点转发能耗负载且更多新增覆盖节点数量的转发行为。仿真结果表明，MC-SCA与典型的随机父节点选择算法（RPNS-A）相比其广播总能耗平均降低了24.23%，而CB-SCA与RPNS-A、MC-SCA以及最小节点负载优先的贪心算法相比其节点最大广播负载值分别平均降低了48.69%、65.21%和10.64%，因此CB-SCA具有更好的广播能量公平性。

关键词: 无线传感器网络, 非对称占空比, 广播调度, 能量效率, 负载均衡