基于有向树算法的无线传感器网络应用研究

缪德俊 于标

摘 要：层次型网络具有覆盖度高、扩展性好和可靠性高的优点，受到广泛重视。但其汇聚节点附近的簇首生命周期短，成为制约它应用的瓶颈。已有研究表明，有多种簇首选择与路由生成方法，存在一定随机性和试探性。一个好的网路拓扑是改善此类问题的基础，提出一种有向树分簇算法。汇聚节点与检测节点是同构的，节点通信半径在几十米范围内，构建一种层次型网络。上层网络拓扑为退化的有向树结构，降低上层网络的复杂度。下层网络拓扑是一种交叉形星型结构。设置簇首传输数据次数，在簇内依次轮换成员节点为新簇首，均衡了簇首能量消耗。网络拓扑在节点无线信号有效半径内侦测构建，最大可能地覆盖了节点分布区域。节点路由特征数据明确，计算量小，易于工程实现，有一定应用价值。

关键词：分簇算法;有向树;交叉形星型;拓扑;路由;簇首

0    引言

无线传感器网络的结构一般有层次型结构、平面型結构、混合型结构和网格（Mesh）型结构。层次型网络结构是一种分级结构，由上层网络和下层网络两层组成。簇首节点担负网络数据传输任务，距汇聚节点越近的簇首，其数据传输量越大，能量消耗也越快。如何节省簇首节点的能耗，延长其生命期已有许多研究，取得了一些改进，但此问题并未完全解决。簇首节点分布的合理性和生命周期是层次型网络构建的关键问题，主要表现在分簇方法及网络拓扑控制算法上[2]。本文提出一种有向树分簇算法，根据无线信号有效半径侦测簇首节点和成员节点，为汇聚节点建立尽可能多的有向通路。提出在汇聚节点无线信号侦测范围内布置的节点，均作为簇首节点使用，称为第一级簇首节点。第一级簇首节点各自与汇聚节点建立一条有向通道，作为通道的第一个首节点，由此获得多条通信路径，利用第一级簇首的数量延长簇首的生命期。第一级簇首节点侦测到的所有第二级节点中，通过节点数量控制与通信能否覆盖分配给第一级簇首节点，成为它们的成员节点。如此，直至新簇首不能侦测到其他节点为止。分簇算法控制了层次型网络拓扑结构和网络性能[1]。这种多条并行数据传输路径，在结构上均衡上层网络簇首节点的能耗，延长了簇首生命周期[3]。簇内节点，按照簇首与上层网络传输数据的次数轮换簇首，均衡了簇首能耗。

1    有向树分簇网络拓扑

设Y个无线传感器节点组成一个顶点集合，定义顶点集R={r0， r1，…，rx}，U={u00， u10，…，uij}与V={v00，v01，…，vkl}分别是R的两个子集。定义图D=（R，E），E（D）={e0，e1，…，ep}是有序集R×R的一个子集。定义uij为第i层（i=1，2…，m），第j个（j=0，1，2…，n）簇首节点，m和n为不确定自然数。定义vkl表示第k层（k=1，2…，f），第j个（j=0，1，2…，g）成员节点，f和g为不确定自然数。退化有向树分簇网络拓扑如图1所示。

1.1  上层网络拓扑

簇首节点能量较易耗尽，本文提出构建多条有向通路的设想，从网络拓扑结构上延长簇首节点的生命周期。定义退化有向树T=（R，U） ，如图1中粗线所示。退化有向树T最末层是出度为0的叶子，是一棵只有树干的退化有向树。退化有向树T降低了上层网络复杂性，简化了路由算法，提高了信息传输的速度。相邻的两个簇首节点，使其只有一条弧bxj关联。对图T中的顶点uij定义弧集B={bxj|x∈（0，1，2，…，m）， j∈（0，1，2，…，n）;d（uxj，uyj） ≤min（dx，dy），y=x+1}。在弧集B中，d（uxj，uyj）为顶点uxj与uyj之间的几何距离，（dx，dy）为uxj与uyj顶点的通信半径。图T中的任一条有向链u00u1ju2j…uij，由无线信号侦测自然选择，形成一条有向通路[4]。任一成员节点vkl都能经簇首节点uij到达汇聚节点。

1.2  下层网络拓扑

通常下层网络是星型结构，一个簇首节点对应若干个成员节点。簇首节点担负簇内成员与上层网络互传数据的任务，这种结构带来簇首生命期短的问题[5]。簇内节点都作为备用簇首轮换使用，按簇首与上层网络传输数据的次数依次轮换簇首。提出一种交叉形簇结构，在成员节点集V={v00， v01，…，vkl}中，若vkl能被两个簇首节点的通信半径覆盖，则使其成为共有成员。共有成员v03交替使用簇首节点u10和u20传输数据，实现相邻簇间的通信，提供了一定的网络连通度。

1.3  有向树是最优树

图D=（R，E）是无线信号有效半径覆盖范围内一级一级依次建成的，顶点集R={r0， r1，…，rx}中，任一个顶点ri都可以通过相邻顶点连通到其他顶点，所以图D是连通的。若u10与u11的共有成员v04，u10与u20的共有成员v03及ui0与ui1的共有成员v10等顶点不成为共有顶点，只归属于其中的一个簇首，则图D成为一棵树。赋边集E（D）={e0，e1，…，ep}中所有边的权为1，定义图T=（U，E1），E1（T）={t0，t1，…，tq}是边集E（D）的子集。顶点集U={u00， u10，…，uij}中任一个顶点uij都可以通过相邻顶点连通到其他顶点，所以图T是连通的，定义T为有向树。T中连通分枝的长度是无线信号侦测的结果，当侦测不到任何节点时组网结束。有向树算法能得到最大可能覆盖度，连通分枝的长度在满足最大可能覆盖度条件下最短，即每条连通分枝的权是最小的，所以T是一棵最优树[4]。作为上层网络的拓扑结构，是一棵没有树叶的树，称为退化有向树。

1.4  有向树网络构建思路

有向树网络拓扑是一种图，遍历全图可以构造有向树分簇算法网络。在图的遍历过程中，组建上层网络和下层网络[5]。两个簇首节点uxj和uyj之间（y=x+1），无线信号能否相互覆盖是弧存在的必要条件。无线传感器网络的数据传输是基本功能，覆盖度与信息传递的快捷性是网络重要的性能指标[6]。

2    有向树分簇网络数据链路层与物理层

无线传感器网络的数据传输、数字信号调制等工作是物理层完成的[7]。物理层的功能和性能设计是否合理，决定了节点电路的功能、可靠性和性能指标[8]。本网络采用同构节点电路，遵守了节点电路低功耗、低成本和小体积的设计目标。

设计性能优良的网络介质访问控制方法（Medium Access Control，MAC）是数据链路层的重要任务[9]。节点身份识别是消除节点间无线信号冲突的关键技术，数据帧中包含频道地址是解决此问题的基础。图2数据帧格式图，它由检测数据、频道地址、网络命令、簇首节点层次号等信息组成。数据帧的意义影响着数据链路层的功能，各数据项定义如下：网络命令与状态字节Z0、簇首与成员标志字节Z1、簇首层次号字节Z2、簇首起点频道接收地址（Z3～Z7）、簇首终点接收频道地址（Z8～Z12）、簇首接收频道地址（Z13～Z17）、温度值字节（Z18～Z19）。定义Z0=（00H～05H）分别为下传数据、上传数据、网络校时、退网、组网、通路建立等命令。定义Z0=（06H～0BH）分别为上传成功、组网未结束、组网结束、节点未入网、节点入网、共有成员等状态。

3    有向树分簇网络网络层

网络层负责路由选择或者路由生成，完成数据融合等工作[10]。本网络节点地址是确定的，节点间无线信号半径相互覆盖。理想情况下，在任一节点与汇聚节点之间都能形成一条通信路径。节点的无线信号半径，地理位置及组网算法影响了入网节点的路由特征数据[11]。

3.1  节点路由特征数据

3.2  有向树分簇网络路由协议

簇首节点组成了上层网络，在汇聚节点和簇首节点间可构成若干条有向通路，作为网络数据传输的路径。传感器检测数据上行至u00是网络的首要任务，u00可将检测数据传至上位计算机或其他网络系统[12]。数据传输方向是两个，一个是汇聚节点u00下行网络命令，另一个是成员节点上行检测数据。

成员节点组成了下层网络，对于簇内数据传输，下行数据时，簇首从其Gx[s]中得到成员接收频道地址，完成发送频道地址配置;数据上行时，成员节点从Fx[5]中得到簇首接收频道地址，完成发送频道地址配置，依级传输直至数据到达汇聚节点u00。对于簇首轮换，现任簇首达到数据传输次数阈值后，从Jx[m]中选择备用簇首发送频道地址，完成发送频道地址配置，发送Dx[5]簇首起点发送频道地址与Ex[5]簇首终点发送频道地址给备用簇首，实现簇首轮换功能。对于相邻簇的通信，共有成员达到传输数据次数阈值后，从Hx[t]中得到相邻簇首接收频道地址，传送到Fx[5]中，完成共有成员相邻簇首发送频道地址配置。

4    有向树分簇算法

汇聚节点u00作为控制节点发布组网数据帧。组网数据帧包括：组网命令（Z0=04H）、u00接收频道地址P0、簇首层次号Z2∈（1，2，3…，f）等。以第一层簇首组网为例说明一层簇首组网结束情况。若第一层有w条有向通路，那么u00有w个首个簇首节点。组网结束条件为P0[1]∩P0[2]…∩P0[w]=1，首个簇首节点组网结束条件从其收到的上传数据帧（Z0=07H）中得到。

5    结语

赋权图T是一棵最优树，是上层网络的拓扑。有向树分簇算法得到的退化有向树T结构简单，路由明晰，均衡了簇首能耗。u00依簇首级次顺序下传数据，簇首将成员节点数据逐级上传至u00。汇聚节点定时发一次校时信息，网络可以时间方式驱动工作。有向树算法简单，易于工程实现。

[参考文献]

[1]KALPNA G，ANIL K V .Comprehensive review for efficient hierarchical routing protocals on wireless sensor networks[J].Wireless Networks，2019（3）：1159-1183.

[2]SHAIMAA A E，ASMAA O.Optimized hierarchical routing technique for wireless sensor networks[J].Soft Computing，2016（11）：4594-4564.

[3]王景娴，陈珍萍，赵政坤，等.无线传感器网络能耗均衡拓扑模型研究 [J].传感技术学报，2017（8）：1246-1251.

[4]王朝瑞. 图论[M].北京： 北京理工大学出版社，1987.

[5]KUMAR A，SHWE H，YWONG K J，et al.Location-based routing protocals for wireless sensor networks：a survey[J].Wireless Sensor Networks，2017（1）：25-72.

[6]張东升.基于路由距离度量的WSN分层分簇路由协议[J].控制工程，2017（12）：2560-2565.

[7]陶志勇，王和章.基于新型聚类的无线传感器网络非均匀分层路由协议[J].计算机科学，2018（3）：117-125.

[8]黄延辉，伊凯，崔更申，等. 基于非均匀分簇的无线传感器网络分层路由协议[J].计算机应用，2016（1）：66-71.

[9]余修武，刘琴，刘永，等. 深井无线传感器网络非均匀分簇路由协议[J].传感技术学报，2018（7）：1097-1100.

[10]王继红，石文孝.认知无线传感器网络分簇路由协议综述[J].通信学报，2018（11）：156-169.

[11]王慧娇，邱赞，董荣胜，等.一种无线传感器网络能耗均衡的自适应拓扑博弈算法[J].控制与决策，2019（1）：72-80.

[12]周新莲，朱泽鹏.无线传感器骨干网络路由算法[J].吉林大学学报（理学版），2019（2）：363-368.

（编辑 王雪芬）