Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (11): 3275-3281.DOI: 10.11772/j.issn.1001-9081.2018040793

Previous Articles     Next Articles

Broadcasting energy-efficiency optimization algorithms for asymmetric duty-cycled sensor network

XU Lijie1,2,3   

  1. 1. School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023, China;
    2. Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023, China;
    3. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing Jiangsu 210023, China
  • Received:2018-04-17 Revised:2018-06-01 Online:2018-11-10 Published:2018-11-10
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61502251), the China Postdoctoral Science Foundation (2016M601859), the Post-Doctoral Fund of Jiangsu Province (1701047A).

非对称占空比传感网中的广播能效优化算法

徐力杰1,2,3   

  1. 1. 南京邮电大学 计算机学院、软件学院、网络空间安全学院, 南京 210023;
    2. 南京邮电大学 江苏省大数据安全与智能处理重点实验室, 南京 210023;
    3. 南京大学 计算机软件新技术国家重点实验室, 南京 210023
  • 通讯作者: 徐力杰
  • 作者简介:徐力杰(1983-),男,江苏盐城人,讲师,博士,主要研究方向:无线传感网、物联网、社交网络、移动与分布式计算。
  • 基金资助:
    国家自然科学基金资助项目(61502251);中国博士后科学基金资助项目(2016M601859);江苏省博士后科研资助计划项目(1701047A)。

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具有更好的广播能量公平性。

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

CLC Number: