基于加权优化树的WSN分簇路由算法
2020-08-24刘一珏
刘一珏， 王 军
(沈阳化工大学 计算机科学与技术学院， 辽宁 沈阳 110142)
随着传感器技术、物联网等技术的发展，低成本、低能耗、多功能的无线传感器技术得到了快速的发展. 无线传感器网络(wireless sensor networks,WSN)因其成本低、部署方便、安全系数高等特点，被广泛应用于各个领域，也成为目前研究的重点[1].由于无线传感器网络中节点能量受限，而且不能随时补充，因此，优化路由算法，使其在网络的构建和路由选择过程中消耗更少的能量是路由算法设计时需要考虑的首要问题.
为了解决无线传感器网络的能耗问题，研究人员提出很多路由算法，如低功耗自适应集簇分层算法[2](low energy adaptive clustering hierarchy,LEACH)、传感器信息系统高效聚类算法[3](power efficient gathering in sensor information system,PEGASIS)、能量有效的非均匀成簇算法[4](energy-efficient une-ven clustering，EEUC)等.LEACH算法是经典的分簇算法，采用依次当选簇头与数据融合[5]的方式来降低节点的能量消耗，增大了网络的生存时间，但是簇头的选取是根据概率随机进行选择，没有考虑节点间的距离和节点的剩余能量，所以，所选择的簇头分布不均衡[6]并且不合理；PEGASIS算法采用贪心算法，在网络中把节点成链，节点只与最近的节点进行通信，最后选取一个链头节点与基站通信，减少了节点间数据传输的消耗，但是形成的链过长，导致传输时间延迟，不适用于实时的场所；EEUC算法采用非均匀分簇的思想，均衡了网络中的能量消耗，增长了网络的生存时间，但根据概率和门限选取簇头，不能保证簇首的高效性.
上述算法都在不同的方面进行了优化，但都没有对簇内的通信代价进行优化，没有将能耗和时延同时考虑.针对上述问题，本文以延长网络生存时间和平衡网络能耗为主要目的，提出节点间数据传输代价，对树型结构进行加权优化并将其应用于分簇路由算法中，以达到减少节点能耗、增长网络生存时间的目的.
1 相关工作
1.1 网络模型
为了更好地进行研究，对网络模型[7]做如下规定：
(1) 节点随机部署在正方形监测区域，部署完成后不能移动；
(2) 汇聚节点位于正方形网络的中心，能量没有限制；
(3) 网络通信信道是对称的双信道；
(4) 节点可以根据RSSI(received signal strength indication)计算两节点间的距离，可以根据需求调整发射功率；
(5) 节点可以根据监测区域的划分感知自己的位置信息，并获得唯一的身份标识.
1.2 能量模型
能耗模型采用经典的自由空间和多路径衰减模型的无线电模型[8].将l比特的数据传输距离d所消耗的能量为
(1)
节点接收l比特的数据所消耗的能量[9]为
ERx=lEelec.
(2)
其中：ETx表示节点发送数据的能耗；ERx表示节点接收数据的能耗；Eelec表示节点发送或接收l比特数据电路消耗的能量；εfs表示节点在放大自由空间模型中的能耗系数；εmp表示多路径衰减模型中的能耗系数.
利用无线数据传输的特点，无线传感器网络路由算法可以让大规模数据能够安全有效地进行无线传输[10].下面将对改进的路由算法作详细介绍.
2 加权优化树分簇路由算法
2.1 路由算法思想
为了解决无线传感器网络中存在的能耗问题，增加网络的生存时间，本文提出一种加权优化树分簇路由算法——WOTC(weighted optimal tree clustering)，对树型网络拓扑结构[11]进行加权优化，形成最小传输代价树型结构，并将其应用于分簇路由算法[12]中.
WOTC主要思想是：先对监测区域进行分区；然后在分区内的各个节点根据自己的通信范围建立自己的邻居表，再以数据传输代价为依据，在分区内构建加权优化的树型结构(树形结构分为树干、树枝、树叶节点三层结构)；最终数据从各个节点传输至分区内树型结构的根节点，即此分区的簇头节点，并由簇头节点将数据传送至汇聚节点.下文中簇头节点即为分区内树的根节点.通过对监测区域进行分区并将改进的最小传输代价树型结构应用于分簇路由算法中，解决了普通节点与簇头距离过长导致的数据传输能耗问题，也有效防止了树的深度过大导致的长链问题[13].
2.2 路由算法的计算方法
2.2.1 最小剩余能量
在无线传感器网络中，由于节点分布不均匀，在网络拓扑结构中所处的位置不同，所以节点功能和转发的数据量有所不同.如果在设置最小能量阈值时采用同一固定值，则会出现节点过早死亡的情况.于是需分层次设置最小剩余能量阈值.越靠近汇聚节点的节点会转发更多的数据，其单位工作时间内消耗更多的能量，其最小剩余能量阀值应该越大.本文对文献[14]的最小剩余能量进行改进，将节点的子节点数目考虑在内，则任一节点最小剩余能量为
(3)
其中：E0为初始能量；di为节点在树形结构中的层次；b为子节点的数目；a为调整取值的系数.用Eres表示节点剩余能量，当Eres 2.2.2 数据传输代价 改进的WOTC算法拓扑结构的建立首先需要计算节点之间的数据传输代价，即将链路上节点的剩余能量、相邻节点的距离、与基站的距离及信道质量进行综合考虑，计算出数据传输需要消耗的资源数值.数据传输代价越小，说明节点间的路径越有优势.每个节点都会计算与相邻节点的数据传输代价.这样能够更全面地反映链路的状态，更好地反映数据传输的情况.数据传输代价用W表示.表1为计算W的参数. 表1 数据传输代价参数 W计算公式如下： a3Dis+a4D. (4) 其中: (1)a1～a4表示非负权重系数，四者之和为1.权重系数的选择采用层次分析法确定，整合研究人员的主观判断，使定性分析与定量分析相结合，更好地表示出影响因素所占的比重.经计算得出：a1=0.45，a2=0.25，a3=0.25，a4=0.05. (3)Dis为节点与基站的距离，与基站距离较近则消耗能量较少. (4)D表示与相邻节点的距离，与相邻节点距离越近则传输能耗越少. 定义节点j的邻居节点数N(i)： (5) 当节点i与节点j的距离小于节点的通信范围并且节点i的能量大于0，则认为节点i是节点j的邻居节点. 随着网络节点不断传输数据，节点的状态会发生改变,节点间的数据传输代价也会变化，当网络结构发生变化时会重新计算其传输代价. 在理论上，传感器网络的数据传输代价表示两个节点之间的欧几里德距离，但如上面所示，必须考虑到节点的状态，如剩余能量、传输过程中造成的路径损耗和信号衰减、与基站及相邻节点的距离等，所以对传输代价的计算方法进行了定义.传输代价越大表示其传输成本越大，路径消耗也就越大，不是最优路径. 2.3.1 区域的划分 为了减少树型结构的深度，避免长链及坏链的形成，WOTC算法首先对监测区域进行划分，即对监测区域进行分簇. 考虑节点分布的密集程度，依据区域中节点的密集度,动态对监测区域进行划分.首先,将监测区域分为4个相同的正方形区域，用分区号1～4来表示，并将分区号存入节点的区域标记中.其次，汇聚节点在监测区域的中心位置.最后，计算各区域节点的密集度，用单位面积的节点数来表示. 其中子分区数即为簇的数目，节点在各分区内自组织形成簇.在网络初始化时，规定以汇聚节点为原点，建立横纵坐标轴来确定各节点的相对物理位置，并获得各自的物理地址，即节点唯一的ID.节点形成树型网络拓扑时分配树型结构的地址，用于区分节点的层次及类型.各个节点将自身感知的位置信息发送给汇聚节点，来获得自身所处的分区信息，以便汇聚节点更好地掌握网络中节点的分布情况，为之后网络结构的形成提供条件. 分区的结构如图1所示.监测区域被划分为1～4区域，每个区域为一个簇，簇内节点自组织形成网络.如果某一区域的节点过于密集，即节点密度大于额定值(额定值由监测区域的总面积和总节点数来确定)的1.5倍时，则对该区域进行再次分区，将此区域分为2个大小相等的三角形区域.按照这种动态划分规则将整个监测区域分为较小且能覆盖全部监测区域的子区域.图2为对节点密度过大的区域1进行重新分区的示例. 图1 区域划分 图2 区域二次划分 此时区域1由于节点密度过大被重新划分为2个子区域，区域内的节点根据所处的位置重新进行区域的标记，并且子区域内节点自组织形成网络结构. 2.3.2 邻居表建立 首先，位于监测区域中心的汇聚节点以可以覆盖整个监测区域的功率向网络中的节点发送测试报文；然后，区域中的各个节点根据接收到的报文功率的大小及方向确定自己距离基站的距离及自身所处的区域. 当区域划分完毕后，节点首先向周围节点广播自身信息，其广播报文格式如下： TypeS_IDEnergyDis 其字段信息如下： Type：表示报文的格式； S_ID：本节点的ID； Energy：本节点的剩余能量； Dis：与基站的距离. 所有节点都向周围邻居节点发送此广播信息.当邻居节点收到此信息后，首先在邻居表中搜索是否存在此节点，如果节点在邻居表中不存在，则节点根据接收到报文信息的功率计算距离本节点的距离，把此节点信息加入到邻居表中，并且把邻居数加1.然后发送反馈信息给源节点，源节点同样根据信息的功率计算与邻居节点的距离，存入自己的邻居表中，并且邻居数同样加1.节点的邻居表中字段结构如下： NeighborIDLevelEnergyDisDType 邻居表中各字段信息段如下： NeighborID：邻居节点的ID； Level：节点在网络结构所处的深度，即节点在树型结构中所使用的地址； Energy：节点的剩余能量； Dis：节点距离基站的距离； D：与邻居节点的距离； Type：节点之间的关系，如父节点、子节点、其余节点. 此时Level值为空，因为此时还没有形成树型结构，所以该信息字段为空.当形成树型结构时，根据节点在树型结构中的深度和加入树型结构的先后顺序，计算其虚拟的网络结构地址，存入此字段；Type字段为空，当形成树型结构时，节点根据是父节点、子节点或是其他节点将此信息存入此字段. 当节点范围内的其他节点都加入各自的邻居表后，邻居搜索过程完成，进入生成树的构建阶段. 2.3.3 簇内生成树结构的建立 在节点邻居表完成后，便开始生成树的建立.此时各区域中的节点首先选取簇头，然后计算节点间的数据传输代价，并建立加权优化的树型拓扑结构.具体过程如下： (1) 簇头的选取 在改进的WOTC算法中，网络拓扑结构规定簇头直接与汇聚节点进行通信，将本簇中收集的数据发送出去，这种通信方式决定了簇头节点本身的能量消耗高于普通的节点.如果簇头距离汇聚节点太远，则导致能量快速消耗，造成簇头节点的过早死亡.这样网络就会频繁进行网络的重构，降低网络的可用性.所以簇头作为生成树结构的根节点，其选取的机制是将靠近汇聚节点且能量高的节点作为树的根节点. 簇头节点选取如图3所示. 图3 簇头的选取 簇头节点为距离汇聚节点较近且能量较高的节点，在与汇聚节点进行数据传输的时候能够减少数据传输过程中消耗的能量，增加网络的生存时间. (2) 生成树的建立 当节点邻居搜索过程完成后，节点根据上节所定义的计算方法计算节点间的数据传输代价，然后据此构建生成树结构，此树结构分为树干节点、树枝节点、树叶节点.先生成树干，然后再生成树枝和树叶节点. (a)树干节点建立 按照上节定义的簇头选取方法选取各区域的簇头，然后从簇头开始，根据计算的数据传输代价，选择向最小数据传输代价的节点发送请求消息，请求加入树干，并把自己的Level值设为1.当节点满足最小剩余能量的要求时，则加入树干，将本节点的Level值加1，并且在之后用点分隔再加一位表示加入的顺序.例如，除了簇头之外第一个加入树干的节点其Level值为2.0，表示是树型结构的第2层，并且是第一个加入第二层的节点，为树干节点，分隔符点之后为0的都表示树干节点.然后节点将上一跳节点即簇头节点的Level值存入邻居表，把Type字段也存入自己邻居表，簇头节点为此节点的父节点，所以在邻居表中存为isfather.至此，节点邻居表中的数据字段全部填写完成. 此节点再向自己邻居表中的数据传输代价最小的节点发送请求加入消息，满足要求后加入树干，并且将自己Level值更新为3.0，将上一跳节点的Level值存入邻居表，上一跳节点也同时将此节点Level值存入邻居表；然后在邻居表中将上一跳节点的Type字段更新为isfather，同时上一跳节点在邻居表中把本节点的Type值更新为isson.按照此方法进行树型结构中树干的构建，直至最后一个树干节点加入.在此以一个区域为例，其树干节点结构如图4所示. 图4 树干节点 图4节点中标记的值为节点的Level值，即在树型结构中所处的深度.其中1为此区域的簇头节点，2.0表示深度为2，且第二个加入树型结构的树干节点，依次类推，8.0为深度为8，且最后一个加入树型结构的树干节点.至此，树干结构构建完成. (b)树枝节点的建立 当树干节点构建完成后，节点向周围节点广播自己当选树干节点的消息.周围节点接收到此信息后，在自己邻居表进行搜索，当树干节点是邻居表中数据传输代价最小的节点时，节点向树干节点发出请求加入的消息，当满足剩余能量最小的要求时，成功加入树型结构，并且其Level值为其连接的树干节点即其父节点的Level值加1，分隔符后根据其加入树型结构的顺序进行编号1、2、3等.比如与Level值为2.0的树干节点相连接的第一个树枝节点，其Level值为3.1，表示其树型深度为3，是第一个加入此树干的树枝节点，直至所有树枝节点加入树干.其结构如图5所示. 图5 树枝节点 图5中所有分隔符后为0的为树干节点，为1的为树枝节点，空白的为未加入树型结构的节点. (c)树叶节点的建立 当树枝节点建立完成后，节点同样向邻居表中的节点发送广播消息告知自己当选为树枝节点.邻居表中未加入树型结构的节点对邻居表进行搜索，当数据传输代价最小的节点为树枝节点时，未加入树型结构的节点向此树枝节点发送请求加入的消息，当节点满足最小剩余能量的要求时，加入树型结构，成为树叶节点，其地址为上一跳树枝节点即父节点的深度加1，并且再增加一位标志位，并根据加入的顺序进行编号，以区分不同树叶节点.如4.1节点第一个树叶节点地址为5.1.1，表示其树型结构的深度为5，为此树枝节点的第一个树叶节点.按照此方法直至所有节点都已加入树结构.当根据树叶节点地址推算其树枝节点地址时，把深度减1，然后去掉最后一位即是树枝节点地址.其树型结构如图6所示. 图6 树叶节点 如图6所示：所有节点均已加入树型结构，树干节点地址为两位并且最后一位为0；树枝节点同样为两位，最后一位按加入树干的顺序排列，图中仅标示出第一个加入树型结构的树干节点，故最后一位均为1；树叶节点地址为三位或三位以上，最后一位为加入树枝节点的顺序，图中仅标示出第一个加入树型结构的树叶节点，故最后一位均为1.至此，分区内的树型结构构建完成. 2.3.4 路由算法的描述 V代表传感器节点，W代表两节点间的数据传输代价，则数据传输的主要步骤如下: (1) 根据上述最小传输代价树型结构，在数据包中增加节点最小剩余能量Emin、节点间的数据传输代价值W； (2) 节点开启一个定时器，接收此时间内收到的Request消息，形成邻居表； (3) 节点根据邻居表中信息计算节点间的数据传输代价，并根据上节所述规则进行处理； (4) 根据定义好的规则建立生成树结构、建立传输路径，进行数据传输. 节点数据传输代价将节点之间距离、距离基站距离、链路质量、剩余能量等参数进行综合考虑.下面为路由算法描述的伪代码： 输入：节点的集合 输出：生成的逻辑树 ForVfrom 1 toNdo T=0 Subregion of nodes Continue； For each vertexV Send Broadcast message to Adjacent node Form a neighbor table based on node information For each vertexV Calculating the cost of data trans- missionWbetween nodes Sort theWof Nodesorder byWin the Neighbor table For(i=1,i<=N,i++) select the next smallestWNode betweenVif(No cycle is creat)T returnT returnT end for 通过这种改进，综合考虑节点剩余能量和节点间距离，确定使用数据传输代价最小的节点来转发数据，均衡了网络整体能耗，提高了数据传输效率. 设定网络中只有一个汇聚节点，与传统的簇树结构不同，先设定两个时间t1、t2,在t1时间范围内时，当一个节点请求加入网络，先分配给节点一个id，然后加入节点的邻居表.过了时间t1，在时间t2范围内时，按上述算法形成拓扑结构，但不再接收加入邻居表的请求，把这些请求消息储存在临时表里.这样会减少能量的消耗，增加传输效率[16].因为如果有请求就重新进行拓扑结构的构建，中间会不断进行重构，会带来地址重新分配等的若干计算，浪费能量，降低效率.拓扑周期流程如图7所示.其中节点接收数据和接收请求，再根据数据包的内容区分为数据还是请求. 图7 拓扑周期 当传感器网络中所有节点状态都正常时，会按照流程运行.如果一个节点在一段时间内由于任何原因与汇聚节点失去联系，将认为该节点已经死亡.当死亡节点是树叶节点，网络继续工作；当死亡节点是树枝节点，则重新选择合适的树枝节点加入树干，在小范围内进行调整；当死亡节点为树干节点，则重新选取树干节点进行代替，并且此树干节点之后的树干节点都要重新进行选取，更新树型结构的地址，在较大范围内进行网络的重构.通过这种方式建立了一个分布式独立的能源高效网络，而且节点间的数据传输代价小. 为了评估改进后算法的性能，应用NS2对经典LEACH算法、EEUC算法及改进算法进行网络仿真分析.其网络环境设置如下：设定仿真环境区域为200 m×200 m，网络中随机分布的WSN传感器节点个数为100个，将节点初始能量设置为2 J，节点发射功率为0.6 W，接收功率为0.3 W，发送数据包大小为512 bit，网络中的基站处于区域的中心位置. 图8中表示了网络中存活节点数量随网络仿真时间的变化情况.由图8可以看出：传统的LEACH算法中出现死亡节点的时间较早，在200轮之后节点开始死亡；EEUC算法在节点能耗方面得到改进，在600轮左右开始出现死亡节点；改进的WOTC网络结构中节点死亡时间较晚，在节点能耗方面有了明显的改进.网络中一半节点的死亡时间LEACH算法最早，EEUC算法次之，WOTC算法最晚.可以看出改进的WOTC结构使网络中节点的能量消耗更加均衡，避免了节点的过早死亡，增加了传感器网络的有效存活时间，很大程度上提高了网络的稳定性. 图8 网络中节点存活数量对比 图9表示了网络能量消耗随网络仿真时间的变化情况. 图9 网络能量消耗随仿真时间的变化 由图9可以看出：随着运行时间的增加，LEACH算法能量消耗最多，EEUC次之，改进的WOTC算法整体的网络能耗最小.WOTC通过对监测区域进行分区、对分区内传输路径的通信代价进行优化并采用加权优化的树形结构，使得网络中能耗趋于平缓状态，平衡了网络整体的能量消耗，提高了网络的性能. 目前无线传感器网络技术已经得到了广泛的应用.本文在经典的WSN路由算法以及改进的研究成果的基础上，提出了一种改进的加权优化树型结构的WSN分簇路由算法.通过计算数据传输代价，对树型拓扑结构进行加权优化，形成最小传输代价树的结构，并应用于分簇路由算法中，平衡了网络的能量消耗，增加了网络的生存时间.由于对数据传输路径进行优化，额外增加了控制和计算的开销，但整体上提升了网络的性能.下一步的研究工作将会在本文研究的基础上，对算法的时延进行优化，增加网络的吞吐量，并进行验证.
2.3 路由算法过程
2.4 拓扑结构声明周期的控制
3 仿真分析
4 结束语
