基于复杂网络的无线传感器网络节能演化模型

1、基于复杂网络的无线传感器网络节能演化模型 朱海林，罗红，北京主要的智能通讯软件和多媒体实验室，北京邮电和通讯大学，P.O.box106，北京100876，PR中国。彭海鹏，李理想，罗群，信息安全中心，网络和开关技术的国家重要实验室，北京大学邮电和通讯系，P.O.box145，北京100876，PR中国。文章信息文章历史：收录于2008年7月21号。摘要 基于复杂网络的理论，在本文中我们为无线传感器网络提出了两个自组织的节能模式，第一种模式是根据连接和每个传感器节点的剩余能量构建无线传感器网络，因此，它可以产生自由规模网络，这种网络能容忍的随机误差较大。第二个模型，我们考虑的是整个网络能源消费更

2、加平衡。最后，我们给出了两种模式的数值实验。1 简介无线传感器网络经常由成百甚至上千个为了检测物理现象而组织在ad-hoc模式中的分布式传感器节点组成。无线传感器网络能覆盖一个广泛的应用区域，因此它们可以很容易地部署和自我组织。无线传感器网络的应用范围从重要的社会问题例如环境和居民区中心的监测，交通管制，紧急情况，以及医疗保健服务等到经济问题如生产控制和结构监测等。由于传感器节点由电池供电，而这些传感器节点又分布在遥远地区，电池跟换变得不合实际应用。因此，在研究无线传感器网络中怎样延长网络寿命是一很重要的问题。最近，在许多科学领域中人们对大型复杂网络的结构和动态非常感兴趣。毫无疑问，实质上很多

3、系统能够用复杂网络模型来描述，这些模型是由许多节点通过连接而构建的，例如互联网，科学协作网络，万维网，代谢网络。事实上，为了寻找一种新的方法来制定战略打击恐怖主义和拓扑意大利机场网络，许多研究已经完成。此外，Barabasi 和 Albert提出了无标度模型，使一个复杂网络随着电能法则分布程度而产生。结果表明，无标度网络在针对节点的随机取消和连接失败时的功能非常强大，但是当很多的被链接的节点做为目标时又显得很脆弱。 近年来，无线传感器网络的许多能源意识和容错拓扑控制算法已经被提出了。在参考【16】中，作者为收集相关数据的传感器网络提出了一种节能路由算法。作者在参考【17】中为聚类传感器在恶劣环

4、境中部署提出了一种构建k -连通网络的方法。参考【18】中，作者提出了一种机制来推断集束头之间的容错通信拓扑。在参考【19】中考虑的几种控制算法是为了在提高网络性能的同时维持网络的连接性。在参考【20，21】中作者讲述了许多关于节能和容错的相关工作。然而，从网络演进和位置分布来看，几乎所有的现有研究还没有研究出在无线传感网络中的节能和容错的表现。在本文中，我们提出了两种基于复杂网络理论的无线传感器网络演变算法。第一个模型，推导能源意识到沟通的拓扑结构，并且该模型可以产生无尺度网络，该网络具有高的随机误差的容忍度。为了阻止在数据传输过程中高度节点快速消耗能量，在模型二中，我们限制了每个节点的通讯

5、连接数目。本文的剩下内容将作如下组织：在第二部分，我们提出了一种能源意识演化模型式算法。在第三部分，我们提出了一种能量平衡演化模式算法。在第四部分，我们给出了数值试验来呈现由上推荐的算法来组成的网络的特征。最后，第五部分给出了本文的结论。2 无线传感器网络的能源意识演化模型 尽管是一种复杂的网络，无线传感器网络有其特殊的功能。因此，我们必须考虑的因素例如：节点传输半径的约束，能源效率，及其容错表现。在复杂网络理论中，局部区域和适应性模型在考虑传输半径和每个节点的能量维持因素的同时，为演进算法的研究给出了一种新的观点。在这部分中，我们将提出能源意识演进模型的第一个算法。在无线传感器网络中，每个节

6、点的能量被消耗在不同的用途中， 节点花费它们的能量最多是在网络已经被组建好后的数据传输过程中。因此，我们认为每个节点的剩余能量是多种的并被固定在我们演进算法的过程中。并且，在无线传感器网络中，在网络中的每个节点只能与在它们传输半径范围内的节点通讯，因此叫做局域网连接。其结果是，每个节点的临节点数目应该经常被约束。为了清晰可见，我们在表1中列举了一些重要参数来表明无线传感器网络的特征。一个网络的生成如下：（1） 增长：首先由少数目的节点（m0），在每个时间步，我们增加一个新的节点（它们将连接到本已在网络中存在的节点上）（2） 选择性的附属： 当一个新的节点进入网络，它将在它的局部区域选择一些节点

7、去连接。我们认为一个新的节点被连接到节点i 依靠的连接系数 ki 的可能性为，此节点的剩余能量为E。在本文中，我们定义一个函数f(E)来说明一个节点的剩余能量与它被连接上的能力的关系。一个节点的能量越多，它被连接到一个新加进来的节点上的可能性越大。因此，这儿的f(E)必须是一个递增函数。例如E, 等，并且的形式是 （1）在复杂的网络中，对于观察网络的特点来说，分布的程度是一个非常重要和有益的因素。用这种算法创建的网络的分布程度，在基于连续理论的基础能够被检测。在Barabasi和Albert提出的方法中，网络的增长被作为一个持续的过程对待，允许用积分算法简化模型。如果要使这种近似的模拟与具体的

8、网络增长非常相似，前提是我们考虑的网络有足够大的规模，即网络经历了大量的时间步。在每个时间单元，m条新边就被形成了，所以我们得到 （2）表1 重要参数的定义在每个节点的局部区域，我们有 （3）此处的L是安装在新来节点局部的节点数目，是f(E)的期望值，k是网络的分布度，在大规模的网络中，平均分布度可一用下面的公式计算 （4）此处的eo和mo分别代表开始时的连接数和节点数，并且它们非常小，将（3）式（4）式代入到（2）式，我们得到 （5）然后我们有 （6）因为f(E)是一个增函数，我们将f(E)=E作为一个例子，然后 （7）最后，我们将展示f(E)的形式确实不影响分布程度特征的最后结果。由于ki

9、(ti)=m， 因此我们得到 （8）一个节点的连接系数ki(t)小于k的可能性是（9）假设我们在相等的时间间隔内加入节点到网络中，在时间ti时的可能性程度是 因此我们得到（10）有剩余能量为E的处于此分布度的节点的可能性密度函数是 （11）为了获得整体概率密度函数， 我们取这些函数的加权平均值来衡量剩余能量的可能性。此外，K是节点持续随机变化的程度，换句话说 （12）此处是E的分布密度，Emax和Emin是剩余能量值的上下限，显然，此式中 ，因此我们能发现在给定的网络中是不变化的。因此，尽管剩余能量分布在每个网络中，电量的分布有一个指数为1的分布形式。因此，我们能用这种能量意识的方法和自由规模

10、的特性来组织无线传感器网络。该算法不仅能够用节能的方法使网络演进，而且使网络增加了抵抗随机误差的程度，这一点继承了大部分自由规模网络的好处。3 能量平衡演进模式在上述的能量意识演进模型中，我们用节能的方式得到自由规模网络的结构。然而，在无线传感器网络中，存在一些传感器节点有很多的能量，这些节点可以连接太多的节点，并且在网络自组织之后的工作时很快地消耗电量。此外，这些节点与许多环相连接，可能变成网络的瓶颈。为了阻止节点连接太多的节点，在本节中，我们提出另外一种算法叫做能量平衡演进模式。在这种模式中，我们假设每个节点能连接超过ki(max) 个节点，并且ki(max)的数值也依靠此节点的剩余能量E

11、。我们还假设有最大能量Emax的节点能连接超过ki(max) 个节点。因此我们容易得到ki(max)= kmaxE/Emax . 与能量意识演进模型算法相比，我们介绍新模型的最大限度，能得到能量平衡演进模型简单介绍如下：（1）增长：首先由少数目的节点（m0），在每个时间步，我们增加一个新的节点（它们将连接到本已在网络中存在的节点上） （2）选择性大的附属： 当选择一些节点与新加入的节点连接时，我们假设一个新节点依靠连接系数ki被连接到节点i 时的可能性为i，节点i 将被连接到超过ki(max) 个节点上，因此 （13）此处我们定义指示了当ki越接近ki(max)，节点被连接到新节点上的可能性越

12、小。当ki接近最大值ki(max) 时，节点i 将再不可能连接到新加入的节点上。 为了得到分布程度P(k)，我们可以使用在EAEM算法中同样的方法， （14）在一个网络中，大部分节点的度ki 远小于它们的最大值ki(max)，相似地，我们得到此处 然后，我们有 （15）一个有剩余能量为E的节点的可能性密度函数为 （16）为了获得整体的肯能性密度函数，我们取这些函数的加权平均值来衡量剩余能量的可能性。然后（17）此处是E的分布密度，对于节点度来说K是不断随机变化的，Emax和Emin是剩余能量值的上下限。 在此模式中，p(k)是多样的，并且随着能量的不同分布而相应变化。尽管，网络结构不是自由规模

13、的，但是它比前一种算法更能平衡整个网络的能量消耗。在kmax的极限情况下，环的限制被删除了，这时，EBEM算法与EAEM算法相当。4 数值实验在网络演进过程中，我们假设网络从m0个节点开始m0=5，在每一步，一个新节点被连接到已经存在的节点中的三个节点上。在两个算法的演进过程中，我们假设每个节点的能量从0.5 J到1 J变化，在我们的实验中，我们检测三个不同的剩余能量的分布。分布函数和相应的期望值如表2所示。为了检测通过EAEM创建的网络的特性，在下面，我们将分析连接性和分布度随时间的演进。从图1到3我们能看出能量分布、局部区域、节点加入的时间等因素是怎样影响节点连接性的增长。图1显示了能量分

14、布在连接性增长中的影响。当分布度被给定时，各种变化的期望值将产生不同的连接性增长速度。图2预测最近加入到网络中的节点基于局部区域节点数量的基础上将选择不同数目的节点。当L较小的时候比L较大的时候，节点被连接的可能性更大。因此，当L较小的时候，连接性将相应增加得快些。图3表明了一个节点加入到网络中的时间ti 对连接性增长的影响。Ti越小，节点加入得越早。因为这早就加入的节点有更多的时间被选择连接到新加入的节点上，它的连接性ki(ti)比那些后接入的节点的连接性增长得快。图4显示了网络通过EAEM模式分布度的产生。我们发现不管剩余能量如何分布，程度分布有电能法则的形式。我们发现分布度有power-

15、law形式尽管是剩余能量的分布。这表明我们通过这种算法在任何条件下能得到自由规模网络。因此，当用EAEM算法组建网络时，我们不需要严谨地考虑剩余能量的形式。并且，尽管在传感器节点中的剩余能量是多种的，但由此产生的网络总是有一个好的误差容忍度。下面，我们将分析用EBEM算法组建的网络的特征，这些特征可能与用EAEM算法组建的网络的特征不同。从Eq. (17),中，我们发现由于不同的能量分布，使得分布度是多样的。并且很难得到一个普遍的最后结果。为了呈现连接性和分布度对时间的演进，我们研究能量的分布是统一的情况。假设有最大能量Emax的节点几乎能连接最多的节点kmax=20。图5显示了当剩余能量分布

16、是相同的时候用EBEM算法组建的网络的分布度。由于最大度的限制，有很大分布度的节点将很慢地增加它们的分布度。这种算法阻止了节点进行不期望的电能消耗。因此，整个网络的能量将平衡地消耗。显然，EBEM算法比EAEM算法更能容忍误差，在网络中的许多节点有相当大的度。图6显示了不同大小局部区域随时间演进的连接性。图7显示了由于受一个节点加入到网络中的时间影响的连接性随时间的演进。从图6图7我们能看出由于收到最大度的限制，连接性速度在减缓。图1 不同的能量分布对连接性的影响随时间变化图2 大小不同的局部区域对连接性的影响图3 节点接入不同时间对连接性的影响图4 不同的能量分布对分布度的影响图5 当能量分

17、布相同是的分布度图6 局部区域的大小对连接性的影响图7 节点加入的不同时间对连接性的影响5 结论 在本文中，我们提供两种方法模拟无线传感器网络。第一个被推荐的模型EAEM能以一种节能的方式组织网络，这种模式能产生自由规模的网络，此网络提高了对随机的传感器节点连接失败的容忍度。在第二个模式中，对于每个节点来说最大数量的环被加入到算法中。这种算法能使能量消耗比前一种方法更加平衡。最后，我们给出了关于两种模型的数值实验。这两种模式为无线传感器网络的应用提供了一些有用的指导。鸣谢 这项工作被西方学者归国的中国教育部基金会、国家自然科学基金委员会、国家自然科学基金委员会中研究资助局、香港联合研究计划所支

18、持。参考文献1 Vidhyapriya R, Vanathi PT.无线传感器的能量意识路由。IEEE ICSCN 2007年:54550.2 Wang XF, Chen G. 复杂网络：小区域，规模自由，和超越。IEEE Circ Syst Mag 2003年;第3期:620页.3 Amaral L, Scala A. 小网络的特性分类。美国科学院学报2000年;97:1114952. 4 Girvan M, Newman M. 在社会和生物网络的团体结构。美国科学院学报2002;99:82716. 5 Newman M.一份共同作者的科学网络的研究物理技术快报2001年; 64:16131

19、-2 。 6 Albert R, Jeong H, Barabasi A.万维网的直径自然1999年；401:130-1 。7 Adamic LA, Huberman BA. 万维网的发展动态。自然1999 ; 401:131 。8 Jeong H, Tombor B, Albert R, Oltvai Z, Barabsi A. 代谢网络的大规模组织。自然（伦敦） 2000年; 407:651-4 。9 Latora V, Marchiori M. 复杂网络科学怎样有助于形成打击恐怖主义策略。Chaos, Solitons & Fractals 2004;20:6975.10 Guida M, Maria F. 意大利空间网络的拓扑：规模自由的小区域分形结构的网络Chaos, Solitons & Fractals 2007;31:52736.11 Barabasi A, Albert R. 在随机网络中缩放比例的出现。科学1999 ; 286:509-12 。12 Barabasi A, Albert R, Jeong H. 自由规模随机网络的Mean-field理论。物理修订版A 1999 ; 272:173-87 。13 Li F, Chen GR. 一个局部区域演进的网络模型 。物理2003年; 328:274-86 。14 L