用马尔科夫模型优化分布式最小连通支配集算法  

Optimizing Distributed Algorithm for Minimum Connected Dominating Set with Markov Model

作　　者：汪文勇[1] 向渝[1] 董传坤[2] 杨挺[1] 唐勇[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,四川成都611731 [2]电子科技大学电子工程学院,四川成都611731

出　　处：《电子学报》2010年第10期2441-2446,共6页Acta Electronica Sinica

基　　金：国家发改委CNGI项目(No.CNGI-04-10-1D);国家发改委CNGI二期项目(No.CNGI-09-01-07);国家863高技术研究发展计划(No.2008AA01A303);国家973重点基础研究发展规划(No.2009CB320505)

摘　　要：为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.In order to improve energy efficiency and prolong lifetime of wireless sensor networks（WSNs）,a new distributed algorithm for calculating minimum connected dominating set based on node＇s discrete Markov chain model is proposed.A Markov Model for dominating node and dominated nodes,which is used to predict the nodes＇ energy consumption,is developed.The dominating nodes act as clustering nodes in the network.The algorithm runs multi-rounds.In the beginning of every round,dominating nodes are elected based on nodes＇ degree and energy,and the time this round will last is computed,.After this round,the network will re-elect dominating nodes and run the next round.Simulation results show that,compared to the original algorithm,the new algorithm can prolong the lifetime of the network evidently while balancing energy consumption and increasing energy efficiency.

关 键 词：无线传感器网络 离散马尔科夫链 能量效率 网络生存时间 基于极大独立集的最小连通支配集算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]