邬学军，孟利民，华惊宇，周明华，周 凯

(1．浙江工业大学理学院，杭州310023;2．浙江省光纤通信技术重点研究实验室，杭州310032)

无线传感器网络是一种具有全新的信息获取、信息处理与传输技术的通信网络，通常包含大量的可自组织成多跳无线网络的分布式传感节点。无线传感网络具有组网快捷、灵活，且不受有线网络约束的优点，可用于紧急搜索、灾难救助、军事、医疗等环境中，具有广泛的应用前景[1-2]。

降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战。在传感器节点高密度部署的环境中，在保证网络性能的前提下，将最少量的节点投入活跃工作状态，而将其余节点投入低功耗的睡眠状态，是一种节约系统能量的有效方法。如何计算同时满足“覆盖要求”和“连通性要求”的最小节点集合，是一个NP-hard问题[3]。

密度控制是实现上述目的的重要而有效的手段。所谓密度控制，就是在不牺牲系统性能的前提下，将一部分节点投入低功耗的睡眠状态，只保留部分节点作为活跃工作节点。这样，可以降低网络中活跃节点的密度、降低感知数据的冗余性以及减少无线通信冲突和干扰，从而降低整个系统的能量消耗[3]。密度控制可以有效地延长无线传感器网络的生存时间。为保持网络原有性能，密度控制必须满足以下两个条件:(1)保证目标区域的完全覆盖;(2)保证通信网络的连通性，即所有工作节点组成的通信网络必须仍然是连通的[4]。

1 网络节点覆盖模型

在二维平面R2上，节点i的覆盖范围是以节点为圆心、半径等于感知半径Ri的一个圆形区域。本文使用布尔传感模型来模拟传感器网络对监测区域的感知能力。每一个传感器节点有一个确定的监测半径R，并且可以接收半径以内的刺激信号[5-6]。如果一个目标节点位于一个传感器节点的监测范围内，就称为是被覆盖。对于两个分布位于坐标Xi和Xj的传感器节点，如果|Xi-Xj|≤R，则它们是相连的。

假设节点的部署服从泊松点过程，U∈Rn是n维空间的一个子集，A是U的一个非空子族，假定每一个元素A'∈A有容量μ(A)。更进一步，假设大量的“点”分散在U上。本文实际关注的是某个A'∈A的那些点数，这个量表示为N(A)。强度为λ＞0的泊松点过程具有如下性质:

对每一个A'∈A，是一个服从参数为λ·μ(A)的泊松分布随机变量。也就是说，当 A1，···，An∈A各不相交时，随机变量 N(A1)，···，N(An)是互相独立的。对于一个泊松点过程，在μ(U)＞0和N(U)=k的假设下，这k个点式独立的，而且服从在U上的均匀分布[5]。

将上述泊松点过程应用于一个二维区域A，A的面积远大于单个传感器节点覆盖的面积，节点之间相互独立且均匀分布，节点密度为λ，用N(A)表示区域中的传感器数目，它是一个服从以λ‖A‖为参数的泊松分布的随机变量，‖A‖表示区域的面积，可以得到[7]:

为了满足指定的面积覆盖率fa，可以解这个等式来确定需要的节点密度λ。

图1 面积覆盖率与节点概率关系图

当监测半径为10和 fa=95%时，可以解得λ(fa)=0．009 53，区域面积‖A‖ =10 000，所以至少需要95个传感器节点。

2 能量控制的网络优化算法

2．1 网络生成树模型

每个节点在网络中的地位都是相等的，换言之，每个节点都需知道全网的拓扑结构，与此同时，由于节点间频繁的交换路由信息，广播数据可能大量占用网络带宽，并影响节点的发送能力，致使整个网络陷入瘫痪，并消耗大量能量。为解决该问题，一种方法是构建虚拟骨干网，虚拟骨干网的作用类似于有线网络的核心网，可以实现网络数据的交换和路由功能，如果我们将路由数据包强制在网络的一小部分节点上，则由于全局扩散导致的协议开销将会显著减少。另一方面，不在虚拟骨干网上的节点可以进入休眠状态，但可以随时苏醒，并向虚拟骨干网中的节点发送信息[8-9]。

考虑问题中的无向连通图G，一个虚拟骨干网对应于图G中的一个连通支配集。一个支配集满足以下条件:图中的每个节点不是属于支配集就是和支配集中的节点直接相邻。连通支配集是支配集中的点所构成的连通子图。

本文使用一种基于最小生成树的贪婪策略来求解连通支配集。为了最终得到的生成树有更多的叶子节点，也就是说让最后的生成树中有更多的度为1的节点。若生成树有n个节点，这连通这棵树的边为(n-1)条，度之和恒为2(n-1)。因此，在图G中，应该选择度尽量大的节点来逐步构造这颗生成树。然而，仅考虑节点的度来选择节点，对于最后的连通性考虑是不利的。所以本文使用的算法应用如下策略[10-11]:

(1)对图G中的每条边赋权值，边的权值等于该边连接的两个相邻节点的度之和。

(2)从任一节点出发，使用最小生成树算法来求解图G的最大生成树T(即具有最大权值的生成树)，在具体实现中取权值的负值，应用Prim算法。

(3)去掉最大生成树T中度为1的节点，剩下的节点即构成我们所求的连通支配集。

为了分析算法性能，本文构建了一个100×100的传感网络，网络中散落着120个节点。使用上述算法，可以构造的最小生成树如图2所示。

图2 网络最小生成树算法示意图

可以发现，除去此生成树的叶节点后，剩余构成连通支配集的节点如下:3、4、5、7、8、10、12、13、14、15、16、17、18、22、27、30、32、33、35、36、37、39、41、45、47、50、52、53、54、57、59、60、61、64、65、66、69、70、73、75、76、78、79、80、81、87、89、93、95、97、98、99、100、102、104、105、107、110。

在通信模型中，让连通支配集中的点持续工作，让其余点进入休眠状态。这些休眠的点可以随时苏醒，向虚拟骨干网发送信息。这样最大程度地节省了电力，并减小了骨干网中路由信息的交换，保证了网络的畅通。当一个骨干网之外的节点需与另一个节点通信时，我们的策略是让它和目标节点分别与一个相邻的连通支配集中的节点通信，接着在连通支配集中找到它们之间的通路。

2．2 算法性能分析

对算法性能进行分析:(1)算法的无偏性。由于从任意节点出发，都可以得到最优的最大生成树，因此无论哪个节点开始构建生成树，最终得到的连通支配集都不会有偏差。(2)对图中度较大的节点，则根据对边赋权值的规则，与它相接的边都有较大权值，这样这些边被选中的概率就较大，这会导致在一个度较大的节点周围选中较多的边，从而这个节点消耗较多的度，这会使得最终形成的生成树会有更多的度为1的叶子节点。(3)对于图中度较小的节点，根据对边赋权值的规则，与它相连的边的权值相对于与它的邻接点相连的边的权值要小，因此与它相连的边被选中多条的概率就较小，因此它也就可能在最终的生成树中成为一个叶子节点。(4)对于最大生成树的求解来说，存在一种不好的情况，即在生成最大生成树的过程中，若多条备选边的权值相等时，则会存在多棵权值相等的最大生成树。这对我们利用最大生成树来求解连通支配集是不利的。因此，当在生成最大生成树的过程中，若备选边的权值相等时，算法选取依附于当前生成树中度最大的节点的边，这样可以避免一些极端情况的出现[12]。

最后，考虑到由于能量的减少，节点的覆盖范围会减小。本节计算了在不同的覆盖半径下所得的连通支配集节点数。其中的临界值分别是9．22，9．49，9．55，9．99。当覆盖半径小于 9．22 时，节点119不被其它任何节点覆盖。鉴于此，我们提出随节点覆盖半径而改变的连通支配集节点数策略:当电量充足，即覆盖半径为10时，使用上述CDS。当节点的覆盖半径在临界值处变化时，重新计算CDS，得到新的虚拟骨干网，直至某些节点无法被覆盖到，此时整个网络的监测能力也将变化。

图3 通信半径对于连通支配集数量的影响

2．3 能量控制仿真

为了对比说明网络能量控制算法的意义，本文引入网络节点能量消耗模型。传感器节点之间是靠无线电进行通信，发送数据包消耗能量包括发射电路耗能、放大电路耗能两部分，接收数据只有接收电路消耗能量。

发送者和接收者之间的距离d，则发送者消耗能量ETx(l)计算公式为和接收者消耗能量ERx(l)计算公式如下:

其中Eelec表示发射电路和接收电路的能耗，l表示发送数据包包含的比特数，d表示传输距离，εamp和εfs是常数。

本文构建了一个100×100的传感网络，网络中散落着120个节点，每个节点的最初能量为“1”。对比是否使用最小生成树算法，网络节点平均能量变化如图4所示。

图4 网络节点平均能量变化趋势图

3 结束语

本文首先使用基于泊松点过程的布尔传感模型确定了覆盖率与单位面积内传感器节点密度的函数关系，进而求得区域内节点总数，然后利用基于Prim算法的贪婪策略，找到具有最大权值的生成树，构造一个求最小连通支配集的近似解。最后，进一步分析了连通支配集中节点个数与覆盖半径的关系。

[1]孙利民，李建中，陈渝，等．无线传感器网络[M]．清华大学出版社，2005．

[2]郑四海，李腊元．Ad Hoc网络QoS多径路由协议的研究[J]．武汉理工大学学报(交通科学与工程版)，2008，32(3):450-453．

[3]郑祖全．无线自组网技术实用教程[M]．北京:清华大学出版社，2004．

[4]于宏毅．无线移动自组织网[M]．北京:人民邮电出版社，2005．

[5]Garcia-Luna-Aceves J，Roy S．On-Demand Loop-Free Routing with Link Vectors(OLIVE)[J]．IEEE Journal on Selected Areas in Communications，2005，23(3):533-546．

[6]WU X X，Bhargava B．AO2P:Ad Hoc On-Demand Position-Based Private Routing Protocol[J]．IEEE Transactions on Mobile Computing，2005，4(4):335-348．

[7]Anastasi G，Conti M，Gregori E，et al．An Energy-Aware Multimedia Streaming Protocol for Mobile Users[J]．Journal of Pervasive Computing and Communications，2006，1(4):42-50．

[8]薛小平，李欣，张思东．基于路由生存时间的 Ad Hoc Qos路由[J]．北京交通大学学报(自然科学版)，2007，31(2):23-28．

[9]文凯，郭伟，黄广杰．无线Ad hoc网络中基于节点位置的功率控制算法[J]．电子与信息学报，2009，31(1):201-205．

[10]Nabar R U，Bölcskei H，Kneubühler F W．Fading Ralay Channels:Performance Limits and Space-Time Signal Design[J]．IEEE journal on Selected Areas in Communications，2004，22(6):1099-1109．

[11]袁培燕，李腊元．移动模型对Ad hoc网络路由协议能耗的影响[J]．计算机工程，2007，33(11):123-125．

[12]王敏强，郑宝玉．一种新的应用于Ad Hoc网络的能量感知路由协议[J]．南京邮电学院学报，2005，25(1):13-17．