摘要
在节点密集部署的多跳传感器网络中,精确数据收集使得越靠近Sink节点的传感器节点需要承担越多的数据转发量,能量消耗很快,容易造成"热区",缩短了网络生命周期.为了最大化网络生命周期,需要构造生命周期最大的生成树,但这属于NP完全问题.无须知道节点的位置信息,提出一种算法MAXLAT来解决这个问题.算法以一棵Sink拥有最多孩子的生成树为基础,并根据节点负载的大小将树上节点分别定义为瓶颈节点、次瓶颈节点和富裕节点.然后,通过对所有节点进行着色,不断转移瓶颈节点的子孙,到富裕节点的子树上去.算法结束时,得到一棵"瓶颈节点"负载较轻的生成树.实验结果表明,与目前已有算法相比,MAXLAT构造的树具有更长的生命周期.
In multi-hop wireless sensor networks that contain a high density of nodes, precise data gathering makes nodes that are close to the sink incur a heavier workload, which depletes their energy faster and can easily cause a ＂hot spot＂ that would shorten the network lifetime. The problem of constructing a tree that has a maximum lifespan is NP-complete. An algorithm called MAXLAT can be used to solve this problem without the need for the location of nodes. MAXLAT starts from a tree whose root has the largest number of children. The nodes in the tree are classified into three subsets that go accordingly to their respective loads： bottleneck nodes, sub-bottleneck nodes, and rich nodes. Next, the MAXLAT continues to transfer descendants of high-load nodes to sub-trees of low-load nodes by coloring. When MAXLAT is terminated, it constructs a tree in which ＂bottleneck nodes＂ carry a lighter load. Simulation results show that the tree achieved by MAXLAT has a longer lifetime than trees created by previous algorithms.
出处
《软件学报》
EI
CSCD
北大核心
2010年第9期2289-2303,共15页
Journal of Software
基金
国家自然科学基金Nos.60873265
60873188
60903222
国家重点基础研究发展计划(973)No.2008CB317107
长江学者与创新团队发展计划 No.IRT0661~~
