无线传感器网络中使用连通支配集的最小能耗广播算法  

Minimum-energy Broadcast Algorithm in Wireless Sensor Networks Using Connected Dominating Sets

作　　者：黄行波 程红举[1] 

机构地区：[1]福州大学数学与计算机科学学院,福州350108

出　　处：《小型微型计算机系统》2014年第1期74-79,共6页Journal of Chinese Computer Systems

基　　金：福建省自然科学基金项目(2011J01345)资助;福建省教育厅科技项目(2012JA12027)资助;福州大学发展基金项目(2008-XQ-23)资助;福建省科技创新平台项目(2009J1007)资助

摘　　要：广播是无线传感器网络中一种基本而重要的操作,其能耗大小对整个网络性能有着重要影响.在节点传输半径固定的情况下,考虑到无线通信的多向传输等特性,无线传感器网络广播操作中参与转发的节点数越少,则广播操作总能耗也就越小.如何寻找最少转发节点的广播树问题等同于求解图论中的最小连通支配集问题,这是一个NP难问题.本文提出了一种有效的构造最小连通支配集的启发式算法(EMCDS)来构造广播树,在此基础上提出了一种无线传感器网络中的最小能耗广播算法(MEBA).实验结果表明,EMCDS算法能够找到较小的连通支配集,而MEBA算法可依据节点剩余能量来动态选择转发节点,通过实现节点能量的均衡分布来有效延长网络的生命周期.Broadcast is a fundamental and essential operation in the wireless sensor networks. The energy consumption of broadcast operation has an important influence on the network performance. In case that the transmission range of the sensors is a constant value and the broadcasting characteristic of wireless communication is considered, it is seen that the less nodes involved in the relay-and-for- ward process, the smaller total energy consumption resulted in the broadcast operation. The problem to find the minimum forwarding nodes for a given network is equivalent to find the minimum connected dominating set in graph theory, which is a NP-hard problem. In this paper~ we have proposed an Effective heuristic algorithm to construct a Minimum Connected Dominating Set { EMCDS）, and then proposed a Minimum-Energy Broadcast Algorithm { MEBA } for wireless sensor networks. The experimental results have shown that the EMCDS algorithm can find smaller connected dominating set and the MEBA algorithm can dynamically select the forwarding nodes according to the remained energy, and prolong the network lifetime efficiently accordingly by energy balance among the nodes.

关 键 词：无线传感器网络 最小连通支配集 最小能耗广播 网络生命周期 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]