摘 要: 为不平衡能量分布的异构无线传感网构建一种拓扑控制算法 在该算法中，每个节点根据自己的剩余能量和邻居节点的平均剩余能量计算簇头声明报文发送的理论时刻; 在该理论时刻，没收到任何簇头声明报文的节点成为簇头，该簇头广播簇头声明报文; 收到簇头声明报文的节点成为普通节点并放弃发送簇头声明报文 同时，该算法在簇头竞争过程中使用经验数据，并对孤立节点和能量过低节点进行休眠仿真结果表明， 能够延长网络生命周期，有效控制簇头分布密度
关键词: 无线传感网; 拓扑控制; 能量感知; 分簇
无线传感网是由部署在监测区域内大量的廉价微型传感器节点通过无线通信方式形成的一种多跳自组织网络［］，具有广泛的应用 考虑到无线传感网节点能量有限等特点，设计能量高效的网络协议需要设计优化的拓扑控制机制，以提高网络运行效率，减少系统吞吐量
无线传感网拓扑控制研究涉及邻近图方法 概率分析方法优化理论方法分簇算法等，其中分簇拓扑控制算法具有拓扑管理方便能量利用高效数据融合简单等优点 在分簇算法中，网络被划分为多个簇，每个簇通常由一个簇头和多个簇内成员组成，簇内信息经过簇头融合之后再转发至基站［］
不平衡能量分布的无线传感网模型是异构传感网基本模型［］，无论是实验室环境还是实际应用环境条件下，考虑到技术缺陷或环境等因素，传感网节点能量在使用之前使用过程中和使用后都不可能达到完全的平衡，因而不平衡能量分布传感网模型更贴近实际情况
文献［］提出了无线传感网拓扑控制典型的低功耗自适应算法 ，与平面拓扑算法相比，该协议可以延长网络生命期约 ，但是 算法没有考虑能量不平衡问题 在 的基础上出现了很多基于节点剩余能量的拓扑控制算法，文献［］提出了一种基于剩余能量的自适应分簇算法，该算法选择剩余能量最大的节点作为簇头，文献［］提出了基于节点能量阈值的簇头竞争算法，当簇头节点的剩余能量值降低到特定阈值下时，算法就启动新一轮簇的建立过程
在无线传感网实际应用中，异构节点的正确使用可以比较好地平衡网络负载，延长无线传感网生命期文献［］提出了一种异构无线传感网分簇算法，该算法使用功能较强的特定节点作为簇头，并将一个簇分为内外两层，实现了快速分簇和多跳路由 文献［］提出了一种能量有效的双簇头产生算法以减轻簇头负担并均衡网络能耗，该算法在每个簇中选出两个簇头分别承担簇内数据处理和簇外数据通信任务，较好地平衡了网络负载，但是网络大量节点的协调增加了信息交互的负担 文献［］使用异构无线传感网对特定环境进行监测，提出了在考虑能量效率覆盖范围和生命期等因素的情况下网络异构节点的最优比例，但没有处理好能量平衡的问题
在目前所有提出的异构传感网分簇拓扑控制算法中，文献［］提出的 算法是特别新颖和高效的，得 到 广 泛 的 关 注， 算 法 是 一 种 基于能量感知的无线传感网数据收集协议，算法基于邻居节点平均剩余能量与本节点剩余能量的比值，提出了一种独特的分簇方法，形成了比较优化的网络拓扑，延长了网络寿命，并且可以有效地应用于不平衡能量分布的网络场景
问题描述
文献［］提出了一种以邻居节点平均剩余能量与节点剩余能量的比值为参数以节点的度作为另一个参数的分布式分簇算法 分簇算法在一定程度上解决了 算法存在的孤点问题，但 算法还存在以下问题:问题 文献［］所述 算法引入了度的计算，度只对剩余能量大于平均剩余能量的孤点产生有限的影响，网络每一轮运行中的 孤点仍然有可能成为簇头 如图 所示: 节点 为孤点，若节点 成为簇头后会使簇与簇之间产生过多重叠区域，造成分簇不平衡，网络局部簇头数目偏多，从而降低网络效率，耗费能量问题 算法没有及时休眠能量过低的传感器节点，从而加快了能量过低节点的失效，不利于网络平衡问题 算法在每一轮簇头选举之前，各个节点都要为获取实时的 度和邻居节点平均剩余能量信息而在邻居节点之间进行大量的信息交互和数据计算，大量信息的发送和接收造成了能量损失 传感器节点在很短时间内所处环境 邻居节点关系不会有较大变化，节点的时间保持同步，簇头和普通节点信号发射半径固定，大部分节点只能在短时间内不变，这些因素决定了没有必要在每一轮开始时都进行能量信息交互，网络运行过程中可以充分利用经验数据，并在运行若干轮以后对经验数据进行修正，从而减少不必要的能量损耗基于上述方面的考虑，本文在对 算法改进的基础上，提出一种新的面向不平衡能量分布的拓扑控制算法节点能耗模型本文假定无线传感网节点均匀分布在目标区域内，无线传感网节点具有以下特征: 传感器节点具有全局唯一的标识符 ; 传感器节点被部署在目标区域后不具有移动能力; 传感器节点在部署时具有不同的能量分布，且能量不能被补充; 传感器节点不能获取地理位置信息，但能够根据接收信号强度计算发送节点到本节点的相对距离; 除上述特点外，传感器节点的其他参数配置相同无线传感网节点能耗主要涉及传感器模块 处理器模块通信模块等 由于传感器模块和处理器模块的能耗比较低，本文只考虑通信模块的能耗，采用与文献［］相同的一阶无线通信能耗模型 在该模型中，发送 信息且传送距离为 时的能耗公式及接收 信息的能耗公式如下:{( )( )能量感知分布式拓扑控制算法面向不平衡能量分布的拓扑控制算法在 算法的基础上对分簇过程进行改进，避免孤点问 题，及时对能量过低的节点进行休眠包括四个过程: 信息交互簇头竞争节点归属和孤点休眠 在每一轮分簇开始时，各个节点获取自己的剩余能量，并与自己的邻居节点进行能量信息交互 各个节点根据交互的能量信息进行簇头竞争，产生适当数目的簇头节点 新当选的簇头向邻居节点广播消息，各个普通节点根据接收到的簇头广播消息，加入距离自己最近的簇头所在的簇网络在运行过程中保持时间同步 图 为算法流程图在 中，网络节点维护以下数据信息: 节点唯一标志符 节点剩余能量 邻居节点平均剩余能量 上一轮邻居节点平均剩余能量簇内节点 时隙是否为簇头该节点的簇头节点标识符邻居节点列表簇内成员列表当前的轮数等 这些数据信息以特定的数据结构形式保存在节点内存中 节点之间的通信报文包括能量报文簇 头 声 明 报 文 入 簇 请 求 报 文时分报文等具体步骤如下:步骤 信息交互( ) 若网络是运行第 轮，则执行以下动作:网络中各个节点以自己的发射半径 向 邻 居节点广播能量报文 同时，各个节点接收邻居节点发送过来的 能量报文 各个节点根据接收到的 报文，计算出邻居节点平均剩余能量值 ，并保存在各自的数据结构中( ) 若网络运行第 轮，则执行以下动作:网络中各个节点将上一轮计算所得的邻居节点平均剩余能量值 存入另一个数据结构: 上一轮邻居节点平均剩余能量 各个节点以自己的发射半径 向邻居节点广播能量报文 同时，各个节点接收邻居节点发送过来的能量报文各个节点根据接收到 报文，计算出邻居节点平均剩余能量值存入 ，并保存在各自的数据结构中( ) 若网络运行第 轮，则执行以下动作:网络中各个节点将邻居节点平均剩余能量值保存到临时存储器 各节点基于经验数据，即上一轮邻居节点平均剩余能量值 和当前邻居节点平均剩余能量值 ，使用式( ) 来及时更新当前邻居节点平均剩余能量值 各节点完成更新邻居节点平均剩余能量值 后，将临时存储器 保存的值赋给上一轮邻居节点平均剩余能量值( ) ( )( ) 若网络运行第 轮，则执行以下动作:网络中各个节点使用已经存在于内存中的邻居节点平均剩余能量值 和上一轮邻居节点平均剩余能量值 ，基于经验数据，直接使用式( ) 来及时更新邻居节点平均剩余能量值整个网络在后面的运行过程中，在信息交互阶段重复上述步骤，以每 轮为一个单位，前两轮获取经验数据，后两轮在信息交互阶段不再发送和接收报文进行交互，而是直接使用经验数据 所有节点的信息交互过程持续时间为 ，第 轮的节点剩余能量值为节点的初始能量值步骤 簇头竞争各个节点在经历了持续 时间的信息交互过程后，按照式( )［］式( ) 进行簇头竞争或休眠簇头竞争持续时间为( ) 当节点剩余能量大于邻居节点平均剩余能量值时，按照式( ) 计算该节点可能成为簇头节点而发送簇头声明报文 的时刻 所有剩余能量大于邻居节点平均剩余能量的节点在各自的时刻到达时，如果还没有收到任何邻居节点发出的簇头声明报文 ，则该节点向邻居节点广播簇头声明报文 ，声明自己当选为簇头; 否则该节点立刻放弃簇头竞争而成为非簇头节点( ) 当节点剩余能量小于邻居节点平均剩余能量值时，按照下列式( ) 和式( ) 分别计算时刻 和时刻 当 小于 时，该节点在其 时 刻 到 达时，如果还没有收到任何邻居节点发出的簇头声明报文 ，则该节点向邻居节点广播簇头声明报文 ，声明自己当选为簇头; 否则该节点立刻放弃簇头竞争而成为非簇头节点 当 大于 时，该节点进入一轮休眠( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )在式( ) 式( ) 中，为 到 之间的随机数，为簇头竞争的持续时间，为节点剩余能量，为邻居节点平均剩余能量; 式( ) 引 用 自 文 献［］; 式( ) 源于对文献［］的改进，与文献［］中有关公式形式相同，参数意义不同 由上述公式可以得到结论: ( )［］，( ) ，() ，该结论说明簇头竞争阶段持续了 时间，在 到( ) 时间段里，在节点剩余能量 大于邻居节点平均剩余能量 的节点中选出部分簇头节点; 在( ) 到 时间段里，选择剩余能量较大的节点作为簇头节点，并且使剩余能量不足邻居节点平均剩余能量一半的节点进入一轮休眠中步骤 节点归属当簇头竞争结束后，网络进入节点归属阶段，该阶段持续时间为 当普通节点接收到簇头节点发送过来的簇头声明报文 ，该节点根据接收的信号强度计算该节点到簇头节点的距离 每一个普通节点可能接收到一个或多个簇头节点发送来的簇头声明报文 ，该节点选择距离自己最近的簇头节点作为自己的簇头，并向该簇头节点发送入簇请求报 文 网络中各个簇头节点在接收普通节点发送来的入簇请求报文 后，将该普通节点的 加入自己的簇内成员列表，并将不属于该簇的其他节 点 删 除，这样就完成了分簇过程 各个普通节点在成为特定簇的成员节点后，调整自己的信号发射半径为普通节点信号传输半径，以多跳方式与簇头进行通信步骤 孤点休眠在簇头竞争和节点归属的过程中，凡是成为簇头，却没有收到任何入簇请求报文 的网络节点立即放弃簇头身份，进入一轮休眠 凡是没有成为簇头，且没有收到任何簇头声明报文 的网络节点，立即进入一轮休眠仿真分析由文献［］可知，整个无线传感网中实际簇头数量的期望值计算公式为:( )其中， 为簇头数量的期望值， 为网络覆盖区域的面积，为簇半径下面以 算法和 算法为对象进行仿真 和 分 析，仿 真 平 台 为［］参 照 文 献［］，本文仿真采用高密度和低密度两种场景，具体仿真参数配置如表 图 和图 给出的仿真结果是 次独立仿真结果的平均值表 仿真参数参数 值网络大小汇聚节点位置 随机节点数目 ，普通节点信号半径簇头覆盖半径每一轮持续时间报文大小初始能量 离散均匀分布，( )( )( )图 给出使用 个节点进行低密度节点布局的仿真实 验 结 果 由 该 图 可 知，当簇半径较小时，算法产生的簇头节点数目小于 算法产生的簇头节点数目，这是由于当簇半径较小时，簇头广播簇头声明报文 的范围有限，导致网络中存在一定数目的孤点 算法休眠了这些孤点，而 算法则使这部分孤点成为簇头; 算法休眠部分低能量节点，减少了可能参与簇头竞争的节点数目 当簇半径较大时，算法产生的簇头节点数目小于并且接近算法产生的簇头节点数目，这是由于随着簇半径的增大，孤点对簇头竞争的作用减弱，同时算法休眠了部分能量较低的节点，使 得算法中可能参与簇头竞争的节点数目在概率上低于 算法 可见， 算法可能产生的簇头数目比 算法更贴近理论值由图 可知，在使用 个节点的高密度场景下，仿真数据仍然接近理论值，说明在节点密度达到一定程度后，可能产生的簇头数目不会随着冗余节点的增加而增加 当簇半径较大时， 算法产生的簇头数目非常接近甚至超出 算法产生的簇头数目，这是由于在簇半径较大时，孤点的影响变小， 算法虽然休眠了部分节点，但网络中仍然存在冗余节点，这些因素使得 算法和 算法产生的簇头数目非常相近; 此 外，算法及时休眠不必要工作的节点，使得网络能量更趋于 平 衡，随 着 网络节点一一失效，网络能够在较长时间继续保持较多的节点进行簇头竞争，从而实现 算法产生簇头数目接近超出 算法产生簇头数目的可能综上所述， 算法延续了 算法的分布式并行算法的特性，选择剩余能量比较突出的节点作为簇头，而不是简单地选择剩余能量最大的节点作为簇头，适合于大规模无线传感网应用算法基于足够短时间内网络节点及其周边环境大致不变的情形，在簇头竞争过程中充分利用经验数据，使得 算法在簇头竞争过程中的信息交互负荷为 算法的一半，这在分簇无线传感网高速按轮运行过程中节省了能耗算 法 对 孤 点进行了休眠处理，避 免 了算法中孤点成为簇头而造成网络局部簇结构重叠的情况，提高了网络的工作效率算法使用式( ) 来处理所有节点的簇头竞争; 算法采用涉及度的公式来对节点剩余能量值 大于邻居节点平均剩余能量值 的网络节点进行簇头竞争; 而本文 算法引用算法中的式( ) ，并在此基础上引入了孤点休眠处理来对节点剩余能量值 大于邻居节点平均剩余能量值 的网络节点进 行 簇 头 选 择，既省去 了 算 法 对 度 的 计 算，也 弥 补 了算法 的 不 足 可 见， 算 法 延 续 了算法和 算法簇头竞争的高效性，而在孤点处理上性能更优算法基于节点剩余能量和节点初始能量，使用一个类似于式( ) 来处理节点剩余能量值小于邻居节点平均剩余能量值 的网络节点;而 算法基于节点剩余能量和邻居节点平均剩余能量，使用了式( ) 和式( ) 来处理节点剩余能量值 小于邻居节点平均剩余能量值 的网络节点 当式( ) 的计算结果 大于式( ) 的计算结果时，说明节点剩余能量 不足邻居节点平均剩余能量 的一半，则该节点进入一轮休眠; 当 小于时，说明节点剩余能量 大于邻居节点平均剩余能量 的一半且小于 ，则 算法选择能量比较突出者作为簇头 可见， 算法比算法对簇头的选择性更加精确，同时又对剩余能量过低的节点进行休眠，利于网络平衡
结论
本文提出了一种基于节点剩余能量的分布式分簇拓扑控制算法 ，该算法注重使无线传感网能量趋向平衡，充分利用经验数据，减少不必要的网络交互，在一定程度上提高了能量利用率和网络生命期 该算法对孤点进行及时休眠，避免孤立节点成为簇头，有效控制了网络的簇头数量和分布密度 同时， 算法充分考虑邻居节点平均剩余能量实时节点剩余能量，比 算法和算法对节点休眠和簇头竞争的控制更精确，同时也更节省能量 本文通过仿真实验验证了 算法产生的簇 头 数 目 优 于 算法产生的簇头数目，并更贴近网络所期望的理论值本文在网络运行中使用经验数据并及时对经验数据进行修正，但目前经验数据的使用并没有固定的模型，在无线传感网实际应用中，不同的情况下应采用不同的经验数据使用模型，否则可能会对网络产生负面的效果
参考文献:［］史倢，陈志，章韵，等一种基于元胞自动机的无线传感器网络拓扑控制方法［］传感技术学报， ，( ) : 张雪凡异构分簇的无线传感器网络拓扑控制［］应用科学学报， ，( ) :［］徐小良，裘君娜异构传感器网络中一种能量有效的簇头选择算法［］传感技术学报， ，( ) : 刘明，曹建农，陈贵海，等 : 能量感知的无线传感器网络数据收集协议［］软件学报， ，( ) :［］周新莲，吴敏，徐建波 : 无线传感器网络中一种能量感知的分布式分簇算法［］计算机研究与发展， ，( ) :
