基于有向图的平面无线传感器网络拓扑的构建

缪德俊, 于 标

(扬州职业大学, 江苏 扬州 225009)

网络拓扑构建是无线传感器网络(WSN)的关键技术,它决定了网络路由效率、数据传输速度、网络覆盖度和连通度等重要网络性能指标[1]。点功率控制型拓扑结构是调节节点的无线发射功率,均衡接收节点数目,减少信息传输延迟等目的[2]。层次型拓扑是无线传感器网络常见类型,拓扑结构一般采用树形结构,或由多个树形结构组成[3]。平面网络拓扑结构简单，但没有控制管理节点,多采用自组织协同算法构建网络,组网算法较复杂,且无法控制网络的拓扑结构。任何无线传感器网络都有明确的应用目的,节点位置应根据被检测对象物理属性与地理范围合理安排。网络的拓扑结构很大程度上与节点地理分布相关,符合应用要求的节点地理分布是获得好的网络拓扑的基础。平面网络传感器节点检测的环境参数也要传送给汇聚节点,由汇聚节点再上传处理。汇聚节点是连接平面网络的通信节点,在组网时可以作为控制节点使用。

有向图算法由汇聚节点发起网络组织工作,对平面网络拓扑构建进行控制。汇聚节点依次发出组网顺序号(以下称为层),在无线信号有效范围内侦测未入网节点,被侦测到的节点与前一层已入网节点联网,成为新一层网络节点。该平面网络在网络拓扑结构上具有顺序性,简化了路由生成。汇聚节点v0侦测到的节点,都作为v0有向链的首节点使用,使v0获得多条有向链,分担第一层节点数据传输任务,延长网络生命期。通过有向图拓扑控制算法,限制终点最多有2个起点,一方面提高终点连通度,另一方面不复杂化网络拓扑。网络数据上传与下传路径相同,方向相反,路由计算量小。

1 平面网络拓扑的数学模型

若有X个无线传感器节点,构成一个节点集合。定义顶点集V={v0,…,vij,…,vrf},vij表示第i层(i=1,2,…,r),第j个节点(j=0,1,2,…,f),f为不确定自然数。U是有序集V×V的一个子集,其元素称为弧。

弧a=(u,v)是顶点u和v的有序偶对,u是弧a的起点,v为终点。定义有向图D=(U,V),图1为有向图D网络拓扑图。

图1 有向图D网络拓扑图

1.1 有向图的覆盖度

图1中任意顶点vij都可由v0到达,有向图D是连通的。若每个终点只有一个起点,如v23起点仅为v11,v36起点仅为v26,有向图D就成了一棵有向树[4]。树型结构具有数据搜索的顺序性、数据存储的分类性与数据划分的层次性[5]。有向图D具有层次性的优点，图中任一条有向链v0v1jv2j…vrj,均成为有向通路。有向链是节点无线信号一层一层构建的,无线信号侦测不到任何节点时组网结束。有向图算法可获得最大可能网络覆盖度,若有向链的长度在获得最大可能网络覆盖度条件下是最短的,则有向图D中任一条有向链的权是最少的,网络通信平均跳数是较少的。

1.2 有向图的连通度

两个相邻的节点之间只需一条通信信道,多信道是为了提高网络的连通度。若有向图D中的顶点u与v之间有一条弧a关联,则满足弧集A={axy|(x,y)∈(0,1,2,…,255),x≠y;d(vx,vy)≤min(dx,dy),x≠y}。在弧集A中,d(vx,vy)为vx与vy之间的空间距离,(dx,dy)为vx与vy顶点的通信半径。树是连通度最小的图,它的任一边都是割边[3]。若树形拓扑的任一个节点失效,则网络不连通。为了提高有向图D的连通度,适当增加图中弧的数量,提高网络的连通度。从通信路径可靠性出发,限制一个顶点最多只有两个起点,是提高网络连通度的一种方案。如图1中的v23和v36各有两个起点,提高了网络连通度,网络结构未复杂化。

1.3 有向图通信节点能量均衡

有向图D可根据图的广度优先搜索算法思想构建。节点vij和vkj之间(k=i+1)是否有弧存在,受条件{d(vx,vy)≤min(dx,dy),x≠y}的限制,由节点无线信号侦测。层与层之间的通信距离取决于节点的通信能力,这在物理上决定了上层通信节点是下层节点传输数据的必然选择[6]。有向图算法搜索出所有可能的上层节点作为通信节点,这些节点同时也是检测节点。如图1中v21、v24、v25、v26和v27是第二层网络的通信节点。处于上一层次的通信节点分担了下层网络数据传输任务,均衡了全网通信节点能量消耗[7]。

2 平面网络数据链路层的配置

无线传感器网络协议栈包括网络层、数据链路层、物理层、传输层、应用层、能量管理平面、移动性管理平面和任务管理平面八个部分[8]。

数据的发送、接收与调制等工作由物理层负责。节点电路的可靠性、能耗和复杂度取决于物理层设计的合理性[9]。在满足网络性能的基础上,低成本、小体积和低功耗传感器节点电路是无线传感器网络设计的一般目标。以nRF24L01无线模块为传感器节点通信模块,该无线收发芯片有125个可选频道,有5个字节的地址编码配置。

数据链路层介于物理层和网络层之间,借助于物理层为网络层提供服务。数据链路层应设计一个好的网络介质访问控制方法,使邻近节点通信冲突减少以至没有,数据帧的定义对此问题有直接影响。本文数据帧定义有检测参数、频道地址、网络命令、节点层次序号等信息[10]。频道地址限定了接收节点的唯一性。图2是数据帧格式图，各项意义如下:网络命令Z0,组网状况Z1,层次序号Z2,Z3接收频道地址最低字节,Z4第一起点频道地址最低字节,Z5第二起点频道地址最低字节,入网状态Z6,Z7和Z8为温度值字节。命令字节Z0可定义为00H、01H、02H、03H、04H、05H,依次是上传、下传、校时、组网、退网、上传成功等命令。Z1为01H表示组网结束,00H表示未结束；Z6为00H表示节点未入网,01H表示节点已入网；Z2为节点所在层次序号。

Z0Z1Z2Z3Z4Z5Z6Z7Z8

3 平面网络的实现

网络层要完成数据融合,负责路由选择或路由生成[11]。网络节点射频频道地址是确定的,节点间的无线信号可能会相互覆盖,网络路由是可以多选的。无线模块的通信能力与组网算法决定了网络的拓扑结构,约束了各入网节点的路由特征数据和网络结构参数。在网络的构建过程中,确定各节点的路由。

3.1 节点路由特征数据

节点路由特征数据是一个结构性数据[10],定义如下:Tx={Px,Fx,Lx,Sx,Qx[n],Jx[m],ADx}。其中ADx是节点x的接收频道地址;Jx[m]是节点x的m个终点接收频道地址数组,m∈(1,2,…,255);Qx[n]为节点x组网结束标记数组,n是未定的自然数,由节点实际地理分布确定,n∈(1,2,…,255)。Fx=Z0,Qx[0]=Z1,Px=Z2,ADx=Z3,Lx=Z4,Sx=Z5。Qx[1]∩Qx[2]…∩Qx[n]=1,是节点x组网结束条件。

3.2 有向图网络路由协议

网络数据的传输通常有两个方向,下行是根节点v0下传命令数据,上行是除v0外的节点向v0上传环境参数。下行时v0从其m个终点Jx[m]中确定要接收命令数据的终点，上行时终点vij从其Lx或Sx中确定上行路由。

基于有向图D的网络拓扑,若限定终点最多有两个起点,那么任一起点的Jx[m]是适量的。下行数据时,依层选用信道,直至数据到达终点。上行数据时,依层使用信道,直至数据到达根节点v0。在传输数据的过程中,若数据发送失败,则逐次返回发送方节点,由发送方重新选择可能的信道发送数据。

3.3 有向图组网算法约束条件

按节点的通信半径,在根节点v0的控制下,逐层广播组网命令,依据图的广度优先算法[12],在通信半径{d(vx,vy)≤min(dx,dy),x≠y}范围内,侦测所有可能侦测到的节点。相邻节点通信半径可能互有重叠覆盖,会出现数据堵塞和竞争频道的问题,导致通信失败。为此对组网程序设计提出如下要求:(1)v0发组网命令F0与层次序号r,r∈(1,2,3…,R)。(2)vij得到层次序号r后,如已入网,则下传r。若无终点,则上传组网结束标志。(3)vij如未入网,则r层组网,上传vij终点ADx至其起点。

3.4 通信模块频道地址配置

定义节点发射频道地址为{D0,D1,D2,D3,D4},节点接收频道地址为{G0,G1,G2,G3,G4},D0与G0都能码分256个节点,(D0,G0)∈(0,1,…,255)。对256个节点而言,令D1=G1,D2=G2,D3=G3,D4=G4。各节点接收频道地址G0由该节点PCB板地址跳线确定,G0=ADx。设根节点v0接收频道地址为{00,EE,EE,EE,EE},则G0=00H。v0发射频道地址为{D0,EE,EE,EE,EE},D0∈(1,…,255)。终点vij(i=1,2,…,r;j=0,1,2,…,f)接收频道地址为{ADx,EE,EE,EE,EE}。对于vij的发射频道地址,分下行与上行两种情况配置。上行时vij的发射频道地址为{Z4,EE,EE,EE,EE},Z4是第一起点的接收频道地址。下行时vij的发射频道地址为{ADx,EE,EE,EE,EE},ADx是终点的接收频道地址。若一个终点的PCB板上地址跳线ADx=08,其接收频道地址为{08,EE,EE,EE,EE}。

4 有向图网络拓扑组网算法

根节点v0是组网控制节点,v0下传组网命令(F0=03H)与v0的接收频道地址G0,发层次序号r,r∈(1,2,3…,R),R是不确定自然数。为说明某一层终点组网情况,以第一层终点组网为例,设第一层有w个节点作为v0的终点,Q1n=00H未入网,Q1n=01H已入网,w个终点组网结束标志用Q1n(n=1,2…,w)表示。那么组网结束的条件为:Q11∩Q12…∩Q1w=1。

4.1 网络组网算法

(1)v0输出数据:F0=03H,G0=00H,Z4=G0,Z2=r,r∈(1,2,3…,R)。

(2)if(Q11∩Q12…∩Q1w=0) then (G0=G0+1,转1) else (第一层组网完成,转3)。

(3)v0输出数据:F0=03H,G0=00H,Z4=G0,Z2=Z2+1。

(4)vij接收到数据帧后,if (Qi[1]∩Qi[2]…∩Qi[n]=0) then (Z3=G0,若是第二起点,则Z4=G0,上传数据至v0) else (转发v0输出的数据,转5)。

(5)vkj(k=i+1)收到vij转发的数据帧,同(4)处理。若vkj是末端节点,Qkj=01H,否则,Qkj=00H,上传Qkj至vij。

(6)vij收到vkj(k=i+1)数据帧,置Qx[n]=Qkj,vij上传数据至v0。

(7)v0收到vij应答数据帧,if (Qx[n]=01H,x节点组网组束) else (转3)。

4.2 数据上传算法

(1)vij发数据帧至起点vkj(k=i-1)。其中Fx=00H,Z3=ADx,Z4=Lx,Z5=Sx,Z2=r,r=i。

(2)vkj未响应,转(3)。vkj响应,发Fx=05H至vij,上传成功。

(3)vij存在第二起点,发数据帧至vke(k=i-1,e≠j),同(1)处理。否则,上传失败。

5 结论

有向图网络拓扑结构上具有顺序性,节点数据的上传与下传路径明确,节约了网络能量,提高了数据传输速度与效率。在节点无线模块有效通信范围内,遍历了所有可能具有2条数据传输路径的节点,适度增加了数据传输的可靠性。该有向图拓扑构建算法使网络的覆盖度与连通度达到尽可能大。该平面网络拓扑控制算法易于工程化应用，有一定的实用价值。