异构无线网络中能耗均衡和延时双优化拓扑控制方法

摘要

本发明公开了一种异构无线网络中能耗均衡和延时双优化拓扑控制方法，包括逻辑邻居选择、链路对称化、逻辑邻居调整三个阶段，对于一个异构无线网络，在拓扑生成或拓扑更新之初，执行前两个阶段，在两次拓扑更新之间执行逻辑邻居调整以延长拓扑更新周期、减少拓扑更新次数。该异构无线网络中能耗均衡和延时双优化拓扑控制方法能实现兼顾能耗均衡和延时，实现对网络拓扑的优化。

说明书

技术领域

本发明属于计算机网络应用和无线网络拓扑控制技术，涉及一种无线传感器网络的拓扑控制技术，特别涉及一种异构无线网络中能耗均衡和延时双优化拓扑控制方法。 

背景技术

在物联网时代，无线传感器网络在沟通物理世界与信息世界方面起着举足轻重的作用。具有RFID阅读器功能的传感器节点能够以无接触的方式读取其无线信号覆盖范围内的物体上的RFID标签信息，以多跳的方式传输到信息中心，实现对物体的查询、监控、追踪。无线组网简单、易维护、前期投资小、易扩展。但是节点以电池供电，能量储备有限，在一些部署环境下，能量无法补充(如野外的生态环境监测)，能量的耗尽意味着网络寿命的终结。即使在能量可补充的环境下(如对大型港口露天货场的监控)，也希望能量能够以某种尽可能均衡的方式耗尽，这样既可以降低充电频率也可以维持两次充电间隔期间的网络性能的稳定性(如减轻可能的能量空洞对网络性能的影响)。已有的相关拓扑控制技术对能耗均衡性的考虑不够全面(如未阐述能耗均衡拓扑一旦形成，能维持多久、如何维护、维护代价与拓扑性能如何折中等问题)，更未考虑对延时的优化。货物的失窃、有毒气体的泄漏、火警等事件的发送对延时有着苛刻的要求。视频监控等应用所需的海量数据传输更是增强了延时保障的必要性。 

异构无线网络通常指多种无线网络技术(如2G和3G蜂窝无线通信网、WLAN、WiMax等)并存的网络，在本发明中，特指由参数异构的传感器节点组成的网络，这些参数包括节点最大发射功率、接收灵敏度、初始能量储备值、处理器能力、存储与缓存能力等。 

发明内容

本发明要解决技术问题是提供一种异构无线网络中能耗均衡和延时双优化拓扑控制方法，该异构无线网络中能耗均衡和延时双优化拓扑控制方法能实现兼顾能耗均衡和延时，实现对网络拓扑的优化。 

本发明为解决上述技术问题所采用的技术方案是： 

一种异构无线网络中能耗均衡和延时双优化拓扑控制方法，包括逻辑邻居选择、链路对称化、逻辑邻居调整三个阶段，对于一个异构无线网络，在拓扑生成或拓扑更新之初，执行前两个阶段，在两次拓扑更新之间执行逻辑邻居调整以延长拓扑更新周期、减少拓扑更新次数。 

所述的逻辑邻居选择包括以下步骤：(节点在确定发射功率时，其所覆盖的所有节点称为其物理邻居，若只考虑能耗优化目标，则减少发射功率可相应减少物理邻居数，此时无需使用逻辑邻居这个概念。在考虑多个目标进行拓扑优化时，节点邻居数就不能只依靠调节发射功率来控制了。在本发明中，为节点取最大发射功率时覆盖的每个物理邻居计算一种兼顾能耗均衡和延时的度量，根据度量值从大到小选择若干节点作为邻居，此时节点应调节其发射功率覆盖到这些邻居，但此发射功率也可能覆盖更多的节点，因此需要逻辑邻居这个概念来特指节点认可的邻居。将逻辑邻居限定到一个合适值，主要是考虑到，只让逻辑邻居参与寻路包的转发，也只有被选择的逻辑邻居参与路由响应包和数据包的转发，因此，逻辑邻居数小可以简化路由选择，但其数量太少则会影响网络连通。) 

任一节点i执行如下算法选择k个最近邻节点： 

1、节点i在时刻t₁使用它的最大发射功率P_t-max，i广播包含如下节点信息的数据包：它的唯一身份标识id_i、最大发射功率P_t-max，i、在欧拉平面上的坐标(x_i，y_i)、初始能量储备E_i、在时刻t₁时的剩余能量 

2、节点i接收它的所有物理邻居广播的包含所述节点信息的数据包，并存储在它的邻居列表N_L(i)中； 

3、节点i分别计算如下值，并存储在它的邻居列表N_L(i)中： 

3.1、为邻居集N(i)中每个物理邻居计算链路度量值； 

对第j个物理邻居，计算链路i→j的度量值Λ_j； 

3.2、为邻居集N(i)中每个剩余能量大于平均初始能量的物理邻居计算第一能耗均衡因子；为每个剩余能量不大于平均初始能量的物理邻居计算第二能耗均衡因子； 

第一能耗均衡因子 

第二能耗均衡因子 其中j表示第j个物理邻居； 为物理邻居j在t时刻的剩余能量； 

E_av，i为N(i)中的所有节点的平均初始能量： M为邻居集N(i)中的节点数，E_j为节点j的初始能量； 

3.3、为邻居集N(i)中每个物理邻居计算延时影响因子； 

物理邻居j对应的延时影响因子Υ_ij，del的计算公式为： t_ij表示节点i到j的通信延时 

3.4、为邻居集N(i)中每个物理邻居j计算链路度量ψ：当物理邻居剩余能量大于平均初始能量时， 当物理邻居剩余能量不大于平均初始能量时，${\psi }_{\mathrm{ij},\mathrm{down},\mathrm{del}}^t=\frac{{\Lambda }_j·{\gamma }_{\mathrm{ij},\mathrm{down}}^t}{{\gamma }_{\mathrm{ij},\mathrm{del}}};$

4、节点i按ψ值从大到小顺序选择k个物理邻居作为逻辑邻居：优先选择具有 的物理邻居，若具有 的节点数小于k，则从具有 的节点中按值从大到小递补；若所有物理邻居数不大于k，则全选； 

5、节点i计算从它到所选择的逻辑邻居所必需的最小发射功率，并将这些功率值以及选择的逻辑邻居信息记录到邻居列表N_L(i)中。(若节点i到其邻居(如节点j)的距离d_ij小于交叉距离d_crossover，则最小发射功率的计算公式为 $P_{t-\min -\mathrm{ij}}=\frac{P_{\mathrm{rx}-\mathrm{thresh}}·{\left(4\pi \right)}^2{\left(d_{\mathrm{ij}}\right)}^{2}L}{G_t{G}_r{\lambda }^2},$否则使用公式$P_{t-\min -\mathrm{ij}}=\frac{P_{\mathrm{rx}-\mathrm{thresh}}·{\left(d_{\mathrm{ij}}\right)}^4}{G_t{G}_r{h}_t^2{h}_r^2},$其中，P_rx-thresh是节点i的邻居(如节点j)的接收灵敏度【接收灵敏度是已知的，每种类型传感器节点都有其特定的灵敏度值，它是设备的一种特性】，L是与传播无关的系统损耗因素，G_t和G_r分别是发射天线增益和接收天线增益，λ是载波信号波长，h_t和h_r分别是发射天线高度和接收天线高度。) 

度量值Λ_j的计算方法为： 角度 是节点i与基站间的连线与链路i→j间的夹角，若节点i不知道基站方位， 其中，γ是路径损耗指数，c由公式c＝d_ij/d_char计算，d_char为特征距离。 

公式 中， 其中，t^b表示节点j转发一个帧长为l的数据帧的时间； 为由节点i为节点j计算SINR值【信号干扰噪声比】，其中，p_e为环境噪声【p_e需要实测得到，也可根据经验估计-单位为瓦特】，ρ_kj∈[0，1]是节点k实际干扰到节点j接收数据的一种概率，即干扰概率，N(j)是干扰源集合， 表示当节点i向节点j发送时，在节点j处收到的信号强度。【 由节点j处的接收设备检测到，单位为瓦特。】 

对于所述干扰概率ρ_kj，它是节点i为节点j的邻居集N(j)中每个节点k计算的干扰概率ρ_kj，其特点是： 

1)为便于节点i计算，N(j)中每个节点k需要记录自身的数据发送情况，并定期汇报节点j，再由节点j提供给节点i使用； 

2)节点k需要记录其每个数据帧传输的开始与结束时刻，由于节点缓冲区的限制，随着时间的推移，删除旧记录，仅保留与缓冲区容量相当的最新记录； 

3)当节点k需要向节点j汇报数据帧传输记录时，加上它为每个数据帧标记的发送时刻，当节点j接收后，立刻转换成自身时钟刻度； 

4)在节点j准备转交这些记录给节点i使用时，再加上节点j自身的发送时刻，当节点i接收后，也立刻转换成自身时钟刻度； 

5)若数据帧较短，忽略发送和接收时间，否则可依据数据帧长度和传输速率计算； 

当节点i将节点k的数据帧发送记录中的时间刻度转换成自身时间刻度后，就可以与自身同时间段的数据帧发送记录进行比对，通过比对，得出重合部分占总比对部分的百分比，使用这个百分比值作为干扰概率ρ_kj的度量，并使用公式ρ_kj＝α·ρ_kj+(1-α)·ρ_kj，new来更新ρ_kj的值，其中，α是一个平滑因子【α一般可取7/8(八分之七)】，它决定了一个老的干扰概率ρ_kj的值所占权重。 

链路对称方法如下： 

任一节点i执行如下算法使它与逻辑邻居间的链路成为对称链路：【链路对称化的理由是无线网络MAC协议的基本要求(如需要反向发送ACK帧)，若链路不对称，则使得无线网络MAC协议实现复杂化。】 

1、节点i在时刻t₂使用它的最大发射功率P_t-max，i广播包含如下信息的数据包：它的唯一身份标识id_i、邻居列表N_L(i)； 

2、节点i接收它的邻居发送的包含上述信息的数据包，并按如下步骤计算具有对称链路的邻居集： 

2.1、节点i检查它的每个物理邻居是否将它选择为逻辑邻居； 

2.2、若是，但它未将对方视为逻辑邻居，则将对方加为逻辑邻居并向对方发确认；否则，等待对方的确认；【确认的作用在于，先行动的节点需要让后行动的相关节点知道已行动的事实以避免重复类似操作，这种确认的内容包括发起节点标识和接收节点标识以及标识这种确认的类型编码。】 

2.2.1、若向对方发了确认，则返回步骤2.1； 

2.2.2、若在等待对方的确认且超时前收到，则返回步骤2.1，否则将对方从逻辑邻居集中删除后，再返回步骤2.1； 

2.3、若不是，则返回步骤2.1检查下一个物理邻居，直到所有的物理邻居都检查到。 

所述逻辑邻居调整的方法如下： 

在两次逻辑邻居选择执行间隔期，任一节点i执行如下逻辑邻居调整方法： 

1、当遇到下列情况，节点i依据单跳链路的能耗P_relay(d)＝(α₁+α₂d^γ)r，其中，α₁＝α₁₁+α₁₂，而α₁₁和α₁₂分别是发射器和接收器电子元器件能耗【α₁₁取26.5nJ/bit，α₁₂取59.1nJ/bit】，α₂是无线放大器能耗【α₂取10pJ/bit/m²(γ＝2)或0.0013pJ/bit/m⁴(γ＝4)】，d是发射器和接收器间的距离，γ是路径损耗指数【γ可有不同的取值，通常在视距范围内，γ可取2，否则取值在2与4之间，在某些情形下，甚至可达到6】，d^γ的意思是d的γ次方；从N_L(i)中保存的该邻居剩余能量值中减去相应的能耗值，并更新其能耗率：【能耗率是通过统计一段时间内的能量消耗量后再除以这段时间得出，用变量f表示；若要考虑能量消耗量的变化历史因素，则使用另一个变量u来表示，并使用公式u＝α·u+(1-α)·f进行动态更新，其中α 

表示历史值所占权重。】【α一般可取7/8(八分之七)】 

1.1、当节点i向某个邻居发送或转发消息包且消息包的最终目的地不是此邻居时； 

1.2、当节点i在接收到某个邻居转发的消息包时； 

1.3、当节点i侦听到某个邻居转发消息包时； 

2、当遇到下列情况，节点i依据公式P_T(d)＝(α₁₁+α₂·d^γ)·r从N_L(i)中保存的该邻居剩余能量值中减去相应的能耗值，并更新其能耗率： 

2.1、当节点i在接收到某个邻居发送的消息包时； 

2.2、当节点i侦听到某个邻居发送消息包时； 

其中P_T(d)为以速率r bits/s发送消息的能耗；α₁₁ α₂·d^γ含义同前； 

3、当遇到下列情况，节点i依据公式P_T(d)＝(α₁₂)·r从N_L(i)中保存的该邻居剩余能量值中减去相应的能耗值，并更新其能耗率： 

3.1、当节点i向某个邻居发送或转发消息包且消息包的最终目的地是此邻居时； 

3.2、当节点i侦听到某个邻居接收消息包时； 

其中P_T(d)为以速率r bits/s发送消息的能耗；α₁₂，r含义同前； 

4、节点i周期性地检查N_L(i)中是否有剩余能量值小于且能耗率大于非逻辑邻居的逻辑邻居节点(我们的思路是想找出满足特定条件的节点i的物理邻居中的非逻辑邻居节点以作为逻辑邻居的替换对象)若有，则在对方确认后替换之(若有多个满足要求的非逻辑邻居，遵循链路度量ψ值大者优先的原则)； 

5、若无或无法得到对方确认或已达到替换次数上限，则执行逻辑邻居选择算法和链路对称化算法进行拓扑调整。【这种拓扑调整是更大的调整，更大的含义是指节点间需要相互交换信息来更新拓扑，这需要更大的能量消耗，而逻辑邻居调整只需依据现有信息即可，由于不进行信息交换，所以能耗更小，与此相比，需要相互交换信息的拓扑更新就称为更大的拓扑调整。】 

【上述5个步骤可以仅执行1次或2次，也可以动态循环执行，以延时大于预设的阈值作为退出条件，因为这里的逻辑邻居调整仅显示考虑了能耗的均衡性而没有显示考虑延时，存在延时不断增大的可能。】 

逻辑邻居数k为5。 

发明的技术构思以及技术路线介绍如下： 

尽管我们的方法可适用于欧拉空间，但为叙述方便且不失一般性，我们考虑一种随机 部署在欧拉平面上的n个节点组成的平面拓扑网络。v表示网络中的节点集，ε表示代表通信链路的无向边集。因此，网络图可表示为g＝(v，ε)。我们也用g_d＝(v，ε_d)来表示含有向边的网络图，其中ε_d表示包含有向边的通信链路集。 

节点集合v中任意节点i具有唯一身份标识id_i，由欧拉平面的x，y坐标确定其位置。i→j表示ε_d中的一条有向边，它的距离表示为d_ij。若节点i和j之间存在无向边，则可用 表示，即 

我们设定网络节点随机分布在一个矩形区域。一种建模这种部署类型的方法是采用二维泊松点过程^[1].节点均等可能地出现在有限区域A的任何地方，在区域A中发现n个节点的概率如下^[1]： 

$\mathrm{Pr}\left[\mathrm{nnode}\sin A\right]=e^{-\lambda }·\frac{{(\lambda ·A)}^2}{n!}---\left(1\right)$

在式(1)中，λ是与网络节点密度相关的泊松过程密度。节点的邻居集i可表示为N(i)： N_L(i)被用来存储N(i)中每个节点的状态，它含有节点身份标识、能量储备、拓扑性能度量参数、与每个邻居通信所需的功率。每个节点都有个最大发射功率P_t-max，而从节点i到j所需发射功率表示为P_t-ij。节点i在时间t的剩余能量表示为 在无线通信中，发射功率P_tx，接收功率P_rx，与收发两点间的距离d和路径损耗指数γ等参数满足如下关系： 

P_rx∝P_tx/d^γ                                                         (2) 

在式(2)中，取决于视距(line-of-sight，LOS)链路存在与否，γ可有不同的取值，通常在视距范围内，γ可取2，否则取值在2与4之间，在某些情形下，甚至可达到6。 

本发明采用文献[2，3]中所使用的无线收发器能量消耗模型。此模型采用可变发射功率来满足最小接收灵敏度需求。大多数已有无线收发器支持多个离散步的可变发射功率级别。无线收发器的能耗主要消耗在数字信号处理、前端电路、功率放大器等器件上。以速率r bits/s发送消息的能耗由下式计算： 

P_T(d)＝(α₁₁+α₂·d^γ)·r                                     (3) 

接收同样消息的能耗由下式计算： 

P_T(d)＝(α₁₂)·r                                                  (4) 

在式(3)和(4)中，α₁₁和α₁₂是常量，其值取决于数字编解码机制、调制和解调、脉冲成形滤波等因素。α₂取决于天线特性、信道条件、放大器功效、接收器灵敏度等因素。两 种广泛使用的无线传播模型是自由空间模型(γ＝2)和双线传播模型(γ＝4)。至于选择哪个模型取决于通信节点间的距离。文献[2]定义了一种决定这个选择的交叉距离(crossover distance)d_crossover，其数学表达式如下： 

$d_{\mathrm{crossover}}=\frac{4\pi \sqrt{L}{h}_r{h}_t}{\lambda }---\left(5\right)$

若节点间的距离小于d_crossover，则选择自由空间模型，否则选择双线传播模型。文献[4]给出自由空间模型中发射功率、接收信号强度、收发节点间距离等的关系式： 

$P_{\mathrm{rx}}\left(d\right)=\frac{P_{\mathrm{tx}}{G}_t{G}_r{\lambda }^2}{{\left(4\pi \right)}^2{d}^{2}L}---\left(6\right)$

在式(5)和(6)中，λ是载波信号波长；L是与传播无关的系统损耗因素；h_t和h_r分别是发射天线高度和接收天线高度；G_t和G_r分别是发射天线增益和接收天线增益；d是收发节点间的距离。在收发节点间无视距链路的区域，双线模型比自由空间模型更准确一些，其数学表达式如下： 

$P_{\mathrm{rx}}\left(d\right)=\frac{P_{\mathrm{tx}}{G}_t{G}_r{h}_t^2{h}_r^2}{d^4}---\left(7\right)$

文献[3]给出了支持多跳通信的线性拓扑无线传感器网络寿命的理论上界。其模型基于特征距离(characteristic distance)d_char的概念计算最优跳数。这个距离值与发射器和接收器硬件以及信道特征等相关。对任何发射节点t，接收节点r，以及它们间的距离D，存在一个最优跳数K_opt，可由下式计算： 

特征距离d_char与距离D无关，可由下式计算： 

$d_{\mathrm{char}}=\sqrt[\gamma ]{\frac{{\alpha }_1}{{\alpha }_2(\gamma -1)}}---\left(9\right)$

在式(9)中，α₁＝α₁₁+α₁₂。 

对任意节点i来说，其邻居j的位置可用以自己为圆心的坐标(d_char·a，d_char·b)表示。坐标值是特征距离d_char的函数。节点i与其邻居j的距离可表示为d_ij＝d_char·c，其中 $c=\sqrt{a^2+b^2}.$

在数据传输过程中，单跳链路的能耗可表示如下： 

P_relay(d)＝(α₁+α₂d^γ)r                           (10) 

节点i到基站能量效率最高路径的耗能可用下式计算： 

P_link-min(D)＝K_opt·P_relay(d_char)                               (11) 

实际上，节点i到基站的数据传输可能不是沿着最优路径，可能是一条距离为D′≥D的路径，可用下式计算： 

$P_{\mathrm{link}}\left(D^{\prime }\right)={\Sigma }_{i=1}^K{P}_{\mathrm{relay}}(c_i·d_{\mathrm{char}})---\left(12\right)$

文献[5]使用下面的式(13)作为从任意节点i到基站的数据传输路径的能量效率的度量，其值越大，能量效率越高，并证明了满足下面的式(14)。 

$\Lambda =\frac{P_{\mathrm{link}-\min }\left(D\right)}{P_{\mathrm{link}}\left(D^{\prime }\right)}---\left(13\right)$

$\Lambda \le \frac{\tilde{a}·\gamma }{{\bar{c}}^{\gamma }+\gamma -1}---\left(14\right)$

在式(14)中， 和 分别是传输路径上a和c归一化的平均值，分别满足如下关系： 

$\tilde{a}=\frac{K_{\mathrm{opt}}}{K}---\left(15\right)$

${\bar{c}}^{\gamma }\le \frac{{\Sigma }_{i=0}^K{\left(c_i\right)}^{\gamma }}{K}---\left(16\right)$

在文献[5]中，对单跳路径，使用单跳参数值替代平均参数值，因此有如下表达式： 

在式(17)中，Λ_j是节点i计算的与其邻居j间链路的度量，角度 是节点i与基站间的连线与链路i→j间的夹角。若节点i不知道基站方位，可用下式估算： 

${\Lambda }_j=\frac{c·\gamma }{c^{\gamma }+\gamma -1}---\left(18\right)$

文献[5]通过引入Υ_j＝e_j/E(这里，E是每个节点的初始能量，e_j是节点j的剩余能量)来考虑能耗的均衡性，因此，对链路的度量可由下式计算： 

ψ_j＝Λ_j·Υ_j                                                       (19) 

在进行拓扑控制时，依据ψ_j选择值最大的K个邻居。若最大邻居数不足K，则全选。但其假设每个节点具有相同的初始能量，这在实际应用中存在局限性。我们改进如下： 

针对任意节点i的邻居集N(i)中的任一节点j，其初始能量为E_j，在任一时刻t的剩余能量为 N(i)中的所有节点的平均初始能量E_av，i可由下式计算： 

$E_{\mathrm{av},i}=\frac{{\Sigma }_{j\in N\left(i\right)}{E}_j}{M}---\left(20\right)$

在式(20)中，M为邻居集N(i)中的节点数。在进行拓扑控制时，优先选择剩余能量大于平均初始能量的邻居。若此类邻居数大于K，则依据式(21)计算的值选择最大的K个物理邻居为逻辑邻居。 

${\psi }_{\mathrm{ij},\mathrm{up}}^t={\Lambda }_j·{\gamma }_{\mathrm{ij},\mathrm{up}}^t---\left(21\right)$

在式(21)中， 由下式计算： 

若剩余能量大于平均初始能量的邻居数小于K，且存在足够数量的剩余能量不大于平均初始能量的邻居，则可依据式(23)计算的值，按值从大到小顺序选择所需逻辑邻居数进行补足。若这类邻居数仍不足，则无需按式(23)计算，而直接选择所有邻居。 

${\psi }_{\mathrm{ij},\mathrm{down}}^t={\Lambda }_j·{\gamma }_{\mathrm{ij},\mathrm{down}}^t---\left(23\right)$

在式(23)中， 由下式计算： 

以上方法可以确保剩余能量大于平均初始能量的邻居成为逻辑邻居的首选，有利于均衡能量消耗。 

在上述改进的基础上，我们进一步把链路延时考虑进去。从文献[6]采用的数据帧传输成功率公式 可知，链路接收端(即节点j)处的信号干扰噪声比(Signal to Interference Noise Ratio，SINR)β_i的值越大，数据帧传输成功率越高。通常一条链路的单程延时包括发送端(或转发端)的发送延时、传输介质上的传播延时、接收端的接收延时。若两个节点间能直接通信，为简化问题起见，则通信延时设定为0，即不计发送 时间、传播时间、接收时间。若两个节点间的数据传输需要通过中间节点转发，则此两个节点间的通信延时取决于中间节点的处理能力之和。因此，我们采用如下公式计算单跳链路的通信延时： 

$t_{\mathrm{ij}}=\frac{t_j^b}{{(1-e^{-0.5{\beta }_{\mathrm{ij}}})}^l}---\left(25\right)$

在式(25)中， 表示节点j转发一个帧长为1的数据帧的时间。在链路i→j上，接收节点j的接收功率值 与发送节点i的发射功率值 的关系，依据从节点i到节点j的欧氏距离d_ij是小于还是大于d_crossover，可以确定其是满足自由空间模型还是双线传播模型。接收节点j附近可能存在其它节点，例如k。在节点i与节点j通信时，节点k的发射动作对节点j造成干扰，且干扰的大小 与节点k的发射功率 之间的关系，依据从节点k到节点j的欧氏距离d_kj是小于还是大于d_crossover，可以确定其是满足自由空间模型还是双线传播模型。在节点i与节点j通信时，其通信链路质量与节点j处的SINR密切相关，也直接影响节点j对数据帧的转发延时。我们提出一种计算SINR值的新方法，它的特点是考虑了潜在干扰源实际造成干扰的概率。依据此方法由节点i为节点j计算SINR值的公式如下： 

${\beta }_{\mathrm{ij}}=\frac{p_{\mathrm{ij}}^r}{p_e+{\Sigma }_{k\in N\left(j\right)}{\rho }_{\mathrm{kj}}·p_{\mathrm{kj}}^r}---\left(26\right)$

在式(26)中，p_e与热噪声、电磁噪声等环境噪声有关，ρ_kj∈[0，1]是节点k实际干扰到节点j接收数据的一种概率。为便于基于局部信息进行计算，这里仅考虑集合N(j)中节点作为干扰源的情况。下面给出一种干扰概率ρ_kj的计算方法。 

当节点i为节点j计算信号干扰噪声比β_ij时，需要先为节点j的邻居集N(j)中每个节点k计算干扰概率ρ_kj。为便于节点i计算，N(j)中每个节点k需要记录自身的数据发送情况，并定期汇报节点j，再由节点j提供节点i使用。节点k需要记录其每个数据帧传输的开始与结束时刻，由于节点缓冲区的限制，随着时间的推移，可删除旧记录，仅保留与缓冲区容量相当的最新记录。当节点k需要向节点j汇报数据帧传输记录时，加上它为每个数据帧标记的发送时刻。当节点j接收后，立刻转换成自身时钟刻度。在节点j准备转交这些记录给节点i使用时，再加上节点j自身的发送时刻。当节点i接收后，也立刻转换成自身时钟刻度。若数据帧较短，可忽略发送和接收时间，否则可依据数据帧长度和传输速率计算。上述方法可较好地适应网络中各个节点间普遍存在的时钟不同步情况。当节 点i将节点k的数据帧发送记录中的时间刻度转换成自身时间刻度后，就可以与自身同时间段的数据帧发送记录进行比对。通过比对，可以得出重合部分占总比对部分的百分比。我们使用这个百分比值作为干扰概率ρ_kj的度量，并使用下式来更新ρ_kj的值。 

ρ_kj＝α·ρ_kj+(1-α)·ρ_kj，new          (27) 

在式(27)中，α是一个平滑因子，它决定了一个老的干扰概率ρ_kj的值所占权重。 

针对任意节点i，我们为任一j∈N(i)引入一个延时影响因子Υ_ij，del，其计算式如下： 

${\gamma }_{\mathrm{ij},\mathrm{del}}=\frac{t_{\mathrm{ij}}}{{\Sigma }_{k\in N\left(i\right)}{t}_{\mathrm{ik}}}---\left(28\right)$

在式(21)的基础上，我们提出如下考虑了延时影响的关系式： 

${\psi }_{\mathrm{ij},\mathrm{up},\mathrm{del}}^t=\frac{{\Lambda }_j·{\gamma }_{\mathrm{ij},\mathrm{up}}^t}{{\gamma }_{\mathrm{ij},\mathrm{del}}}---\left(29\right)$

在式(23)的基础上，我们提出如下考虑了延时影响的关系式： 

${\psi }_{\mathrm{ij},\mathrm{down},\mathrm{del}}^t=\frac{{\Lambda }_j·{\gamma }_{\mathrm{ij},\mathrm{down}}^t}{{\gamma }_{\mathrm{ij},\mathrm{del}}}---\left(30\right)$

若一个节点成为越多其它节点的逻辑邻居，则其需要承担的包转发任务就可能越重，能量消耗也会更快，因此，需要周期性运行拓扑控制程序以维持拓扑性能满足特定的能耗均衡性要求。拓扑更新周期的长短与拓扑性能恶化的快慢程度密切相关，但是现有相关工作对此尚未有一个定量的解决方案。我们提出一种对已形成拓扑的代价可控的动态维护方法以及可预测的拓扑更新方法，其基本思路如下： 

我们的想法是，若能尽量延缓拓扑性能恶化的进程，则能延长拓扑更新的周期，节省拓扑控制信息交换的通信开销和拓扑控制程序执行的时间开销。我们的具体做法是：在任意节点i进行一次拓扑更新后，它不仅需要记住每个成为逻辑邻居的节点的相关参数值，也要记住它的最大发射功率覆盖范围内的其它物理邻居的相关参数值。 

根据公式(10)，我们知道，只要统计实际通信量，就可近似估计能量消耗情况。因此，节点i需要发送或转发数据给哪个逻辑邻居，相应地它就可以更新这个邻居的剩余能量，并更新其能耗率(用来度量能量消耗的快慢程度)。若节点i空闲，则需要侦听它的最大发射功率覆盖范围内的所有邻居发送或转发数据的情况，相应地更新它们的剩余能量和能耗率。从数据帧的源或目的MAC地址可知道哪个邻居是发送者或转发者。 

在有些情况下，如在收发双方都是节点i的邻居时，还能侦听到哪些邻居在接收数据。 这时，接收耗能也要统计。依据这些记录值，可以在节点i的逻辑邻居中出现剩余能量低于且能耗率高于节点i的最大发射功率覆盖范围内的其它任一物理邻居的节点时，考虑进行逻辑邻居的替换。在征得被选物理邻居同意时，方可进行替换。若无法替换，则节点i的逻辑邻居数将趋于减少(或是因某些节点能量的迅速耗尽，或是因将这些节点从节点i的逻辑邻居列表中删除而得不到新的补充)，当低于一定值，将会影响网络连通性，因此，需要重新启动拓扑更新程序。 

由于仅考虑能耗指标进行替换，多次替换后，延时指标可能变得不可接受，至少干扰概率(如ρ_kj的值)的更新情况未能及时反映在拓扑调整中，因此，即使在能顺利替换的情况下，1～2次替换后，也需要重新启动拓扑更新程序。 

尽管上述方法因拓扑更新周期延长而节省了拓扑控制程序执行的时间开销，但也引入了对节点的剩余能量和能耗率进行更新的时间开销。虽然如此，因拓扑更新周期延长而节省的拓扑控制信息交换的通信开销是一种纯收益，而这种纯收益直接体现在网络应用数据吞吐量的提升上。 

我们的拓扑控制方法包括逻辑邻居选择、链路对称化、逻辑邻居调整三个阶段。在拓扑生成或拓扑更新之初，执行前两个阶段。在两次拓扑更新之间执行逻辑邻居调整算法以延长拓扑更新周期、减少拓扑更新次数。只有逻辑邻居参与寻路包的转发，也只有被选择的逻辑邻居参与路由响应包和数据包的转发，因此，逻辑邻居数小可以简化路由选择，但其数量太少则会影响网络连通。文献[5]通过理论分析和仿真给出结论，在网络节点遵循泊松分布情况下，当逻辑邻居数k＞5时，网络连通概率不会再增加。因此，我们也将逻辑邻居数k定为5。通过文献[7]中的如下公式，可以计算在二维泊松分布的网络部署区中保证网络节点1-连通概率为Pr的部署密度λ。 

$\mathrm{Pr}\approx {(1-e^{-\lambda ·\pi ·d_{\max }^2})}^n---\left(31\right)$

在式(31)中，d_max是节点的最大发射半径，n是网络中节点的数量。但此公式是针对节点的最大发射半径同构的情况，在节点的最大发射半径异构时，可以使用各个节点最大发射半径的平均值作为近似代替。 

有益效果 

本发明的异构无线网络中能耗均衡和延时双优化拓扑控制方法在改进已有基于能耗均衡拓扑控制技术不足的基础上，集成对延时优化的考虑，提出新的能耗均衡和延时双优化拓扑控制方法，以满足有延时性能要求的网络应用需要。同时，提出对已形成拓扑的代 价可控的动态维护方法以及可预测的拓扑更新方法，以便于网络应用对拓扑性能的要求、拓扑更新频率、维护代价等考虑因素的合理折中。 

拓扑控制是一种设置活跃的无线网络链路数目范围所必需的技术，且具有维持网络连通和优化网络寿命的作用。通过保障链路的可用性，拓扑控制技术也能维持路由选择的稳定性和降低路由开销。本发明的特点：(1)定义合适的拓扑性能度量以便于较公平地选择中继节点，以尽可能达到网络节点能耗均衡性和端到端数据传输延时双优化的目的；(2)基于已有局部知识推断拓扑更新时机、通过拓扑邻居调整降低拓扑更新频率以减少拓扑维护代价。 

本发明的有益效果(优点)总结如下： 

1)能够兼顾能耗均衡性和端到端传输延时双优化目标； 

2)能耗均衡性优于现有相关方法； 

3)端到端传输延时优于现有相关方法； 

4)由于平均剩余能量均方差小于现有相关方法，所以拓扑更新周期可以延长，有利于降低拓扑维护开销； 

5)由于端到端传输延时抖动值小于现有相关方法，所以有利于保障视频流数据的传输质量。 

附图说明

图1为一种单一网络拓扑下节点平均剩余能量均方差的变化趋势(基于跳数路由)； 

图2为一种单一网络拓扑下节点与基站间平均端到端延时变化趋势(基于跳数路由)； 

图3为一种单一网络拓扑下节点平均剩余能量均方差的变化趋势(基于能量感知路由)； 

图4为一种单一网络拓扑下节点与基站间平均端到端延时变化趋势(基于能量感知路由)； 

图5为综合多种网络拓扑的平均节点剩余能量均方差的变化趋势(基于跳数路由)； 

图6为综合多种网络拓扑的节点与基站间平均端到端延时变化趋势(基于跳数路由)； 

图7为综合多种网络拓扑的平均节点剩余能量均方差的变化趋势(基于能量感知路由)； 

图8为综合多种网络拓扑的节点与基站间平均端到端延时变化趋势(基于能量感知路由)； 

图9为不同节点密度下各方案中平均节点剩余能量均方差比较(基于跳数路由)； 

图10为不同节点密度下各方案中节点与基站间平均端到端延时比较(基于跳数路由)； 

图11为不同节点密度下各方案中平均节点剩余能量均方差比较(基于能量感知路由)； 

图12为不同节点密度下各方案中节点与基站间平均端到端延时比较(基于能量感知路由) 

具体实施方式

下面结合附图和具体实施例对本发明作进一步说明。 

实施例1： 

本方法既可用于网络节点可控部署的环境(如部署在大型港口露天货场区域兼作RFID货物标签阅读器的无线传感器节点)，也可用于网络节点不可控部署的环境(如野外的生态环境监测)。对于后者，我们先考虑100个节点部署在500×500m²的平面区域上形成的网络(即该区域节点密度 各个节点的位置服从泊松分布)，然后考虑在同样的平面区域内将节点数分别增加到200和300时的情况。另外，部署一个sink节点(即基站)于此区域的右上角。 

基站无能量限制，其它节点的初始能量储备具有随机性，但最大值不超过0.5J。为不使问题过于复杂且能着重关注初始能量储备的随机性对不同拓扑控制方法的影响，我们设定网络节点的其它参数都相同，如表1所示。考虑节点的初始能量储备具有随机性的理由是：无论采用什么措施，能耗的不均衡性始终存在，因此，初始时，在指定区域随机抛洒一定数量节点，使用一段时间后会死亡一部分，于是进行补充。如此反复几次后的网络状况可作为一个新网络来看待，即形成了一种节点初始能量储备具有随机性的网络。 

表1网络节点参数表 

在我们的方法中，若每个节点(如节点i)在计算与其邻居(如节点j)间链路的度量时考虑了角度 (即节点i与基站间的连线与链路i→j间的夹角)，则称为方案1，否则称为方案2。同样，在与我们方法进行比较的文献[5]的方法中，若考虑了角度 则称为方案3，否则称为方案4。 

在仿真中，我们随机选择30个节点向基站发送数据(数据发送率见表1)，这些节点在进行路由选择时采用如下两种度量方式：一种是采用跳数，另一种采用链路两端节点剩余能量的平均值。基于前者的路由称为最短路径路由，而基于后者的路由称为能量感知路由。我们仿真100个时间步，在每个时间步内，随机选中的30个节点各发送一个指定长度的数据。对于方案1和2，每5个时间步进行一次逻辑邻居调整，而对于方案3和4则没有逻辑邻居调整功能。 

比较的性能指标为网络节点平均剩余能量均方差和网络节点平均端到端传输延时。网络节点平均剩余能量均方差是指网络中每个节点的剩余能量值与网络节点平均剩余能量值的偏差平方和取均值再开方。网络节点平均端到端传输延时是指所有发送数据的节点与基站之间端到端数据传输延时的均值。 

图1、图3、图5、图7展示了平均剩余能量均方差随仿真时间的变化趋势。从这些图中可见，我们的方案一和二的平均剩余能量均方差都小于现有方案，即方案三和四。这说明我们方案的能耗均衡性要好于现有方案。由于图1和图3是针对单一拓扑情况，因此，不同拓扑间的能耗均衡性表现会有差异，但大体趋势是一致的。 

图5和图7展示的是10种网络拓扑下的能耗均衡性度量的平均值，其中每个拓扑下的数据是其100个时间步仿真结果的平均值，从中可见，我们方案的优势是明显而稳定的。从这些图中，我们也看到，在网络节点采用能量感知路由时，方案一的剩余能量均方差随仿真时间的变化更平缓些，这是因为能量感知路由总是选择剩余能量更多的链路，因而比基于跳数的路由更有利于均衡能耗。 

从图2、图4、图6、图8可看到，网络节点平均端到端传输延时随仿真时间的变化趋势同样显示我们的方案一和二具有优势。图2显示的变化趋势比较有规律，而图4则展示了一种随机性，这是因为图2采用的基于跳数路由选择的数据传输路径比较稳定，各个时间步间的差异性更多是由每个时间步的数据传输路径的总长度造成的。由于图4采用能量感知路由选路，随着各个节点能量消耗的差异化，数据传输路径也难以稳定，因而在端到端传输延时上表现出一种随机性。 

图6和8是10种网络拓扑下数据的平均值，其中每个拓扑下的数据是其100个时间步仿真结果的平均值。从图6中可见，除仿真初期有些抖动外，随后显示出一种很稳定的状态，其原因也主要是基于跳数路由带来的数据传输路径较为稳定。 

从图8可见，方案一、二和三的平均端到端传输延时随仿真时间的变化较平缓，而方案四波动较大，这主要是因为方案四在进行拓扑控制时不考虑延时因素进行邻居选择，加之采用能量感知路由选路导致数据传输路径难以稳定。尽管方案三也不考虑延时因素，但其考虑与基站间的方位角，限制了其选择邻居的范围，数据传输路径的改变不会有方案四那么频繁，因而延时波动也不如方案四大。

图9和11展示不同网络节点密度下各方案的平均剩余能量均方差对比情况。方案三和四无论采用跳数路由还是能量感知路由，变化趋势是一致的(即随着节点密度的增大，平均剩余能量均方差减小)，这主要是其仅考虑能耗和能耗均衡性选择邻居，在网络节点密度大时，选择余地也大，因此，有利于均衡能耗。 

我们的方案的平均剩余能量均方差随网络节点密度的变化不如方案三和四那样有明显的一致性变化趋势，例如，在图9中，网络节点密度增大总体上有利于平衡能耗，但增大到一定值则无效果。这主要是我们的方案考虑了延时因素，而延时也与干扰相关，网络节点密度增大可能造成的干扰也增大，因此，在网络节点密度增大到一定值后，其带来的正面效益就会被负面结果所抵消。 

图11显示，在较大网络节点密度下，我们的方案能耗均衡性效果不如现有方案，这主要是在能量感知路由有利于均衡能耗的环境下，我们的方案由于兼顾了对延时的考虑而 约束了其对逻辑邻居的选择范围。但在较低网络节点密度下，我们的方案具有明显优势。由于实际应用中，网络节点部署过密会增加经济成本，因而高密度的网络不太现实，即使为了容错，部署了冗余节点，也同样会采取轮流休眠的方法，同时工作的节点密度仍不会太高，因此不会影响我们方案的实际应用效果。 

图10和12都一致性地展示了网络节点密度对端到端延时的影响，即节点密度越高对延时影响越大。总体来说，我们方案有利于降低延时，尤其在节点密度较小的情况下。在图10中，我们的方案二在较高节点密度下表现较差，这主要是较高节点密度增加了其选择背离基站邻居的可能性，同时图10采用的基于跳数路由一旦选定路径则较难改变，因此，不利路径的影响较难立刻消失。在图12中，由于采用的是基于能量感知路由，因此，在这种环境下，我们的方案二没有出现上述情况。 

以上仿真表明，在网络节点部署密度不太高的情况下，我们的方案无论在能耗均衡性和端到端传输延时等网络拓扑性能上都具有优势。这种优势来自于我们方案对节点初始能量储备差异性、基于物理干扰模型下节点转发延时等因素的创新建模，以及在前后两次网络拓扑更新期间基于已有局部知识推测进行判决对逻辑邻居进行调整等策略的创造性设计。 

参考文献 

[1]Chao，X.，Dargie，W.，Lin，G.，2008.Energy model for H2S monitoring wireless sensor network.In：CSE‘08：Proceedings of the 2008 11th IEEE International Conference on Computational Science and Engineering.IEEE Computer Society，Washington，DC，USA，pp.402-409. 

[2]Heinzelman，W.B.，2000.Application-specific protocol architectures for wireless networks.PhD Thesis.(Supervisor-Chandrakasan，Anantha P.and Supervisor-Balakrishnan，Hari) 

[3]Timothy，M.B.，Garnett，T.，Ch，A.P.，2001.Upper bounds on the lifetime of sensor networks.In：ICC 2001，pp.785-790. 

[4]Rappaport，T.，2001.Wireless Communications：Principles and Practice.Prentice Hall PTR，Upper Saddle River，NJ，USA. 

[5]Waltenegus Dargie，Rami Mochaourab，Alexander Schill，Lin Guan.A topology control protocol based on eligibility and efficiency metrics.The Journal of Systems and Software，2011，84：2-11. 

[6]G.Bacci，M.Luise，and H.V.Poor，Game-theoretic power control in impulse radio UWB wireless networks，ArXiv e-prints，2007. 

[7]P.Santi.Topology control in wireless ad hoc and sensor networks.ACM Computing Surveys，2005，37(2)：164-194。