一种树型层次结构的无线传感器网络应用研究

于 标

(扬州市职业大学电气与汽车工程学院，江苏 扬州 225009)

一种树型层次结构的无线传感器网络应用研究

于 标

(扬州市职业大学电气与汽车工程学院，江苏 扬州 225009)

针对无线传感器网络的拓扑结构，提出了一种树型层次结构的无线传感器网络。该网络结构可用最少的无线通信跳数进行数据传输，能均衡使用节点电池能量。同时给出了节点位置估算法和数据丢包解决法，设计并验证了该网络的路由算法。该无线传感器网络所用技术成熟、成本低、易于工程实现，具有较好的实用价值，其网络结构具有一定的通用性。

无线传感器网络 传感器节点 网络拓扑结构 算法 路由

0 引言

根据节点是否移动和节点的布置是否可控，无线传感器网络的拓扑结构可分为4类来构建。目前，拓扑结构的控制研究已经形成功率控制和睡眠调度两个主流研究方向［1］。在保证一定的网络连通质量和覆盖质量的前提下，一般以延长网络的生命周期为主要目标，兼顾通信干扰、网络延迟、负载均衡、简单性、可靠性和可扩展性等性能，形成一个优化的网络拓扑结构［2］。

已公开报道的各无线传感器网络路由协议都有一定的条件设定和局限性。简单的路由协议有洪泛协议、恶劣环境中的可靠路由算法、定向扩散协议［3］。无线传感器网络路由的建立和选择与组网密切相关，组网过程决定了所有可能的路由路径。因此，在一个主节点的控制下进行有序的组网是一种实用有效的解决方法。

1 无线传感器节点

无线传感器节点中的无线模块和处理器模块对组网起关键性的作用，两者决定了节点的通信性能和数据处理能力［4］。过于低廉的功能芯片不可能获得优良的通信性能和数据处理能力。本文设计和使用的测温无线传感器节点电路图如图1所示，其性能稳定，工作可靠。其中Address为地址选择电路。

图1 节点电路图Fig.1 The node circuit

无线模块选择了北京迅通科技有限公司基于nRF24L01的产品，通信范围在 30～40 m左右。nRF24L01是一款工作在2.4～2.5 GHz的单片无线收发器芯片，有125个工作频道，每个频道有40 bit的地址选择，具有功耗低、硬件自动应答与重发功能、价格低等特点。处理器选择ATMEL公司的Atmega8L单片机。Atmega8L单片机有512 B的EEPROM和8 kB的可编程Flash，提供1种工作模式和5种睡眠模式，其SPI硬件接口可与nRF24L01直接相联，是一款低功耗、高性能、性价比较好的单片机。电池选择一节7号1.2 V、900 mA的可充电电池。系统采用BL8550/5.0升压芯片将电源电压升至5 V，供DS18B20使用;采用TPS76333电源管理芯片将5 V电压转变为3.3 V电压，供Atmega8L和nRF24L01使用。上述两个电源芯片都具有稳压性能。

2 网络的拓扑结构

一个无线传感器网络的布置总是有具体的应用目标，各节点的位置一般也非随意安排，由均匀布置、信号有效范围相互覆盖等要求来定位。节点的物理属性确定了各节点间的信号是否能通达，故顶点集V={v0，v1，…，vm}必存在一个边数最多的拓扑结构Gmax(V，Emax)，其中，Emax⊂V＆V，为无序积(V＆V)的一个子集。成功的节点布置会使Emax的关联包含顶点集V的所有元素，则该拓扑结构是连通的，但不一定是较易控制和管理的网络结构。由Gmax(V，Emax)可生成不同的子图G(V，E)，其中E⊆Emax。E的选择决定了无线传感器网络的网络属性和网络能力。树型层次结构网络拓扑图如图2所示。

图2 树型层次结构网络拓扑图Fig.2 Topology of tree hierachical network

定义图2的网络拓扑结构为图G(V，E)。其中，V={v0，v1，…，vm}，顶点vi和vj之间只有一条边pij相联。从信号能通达的角度来看，两个无线节点之间只有一种关联。E={pij|i=0，1，2，…，m;j=0，1，2，…，m;d(vi，vj)≤min(di，dj)，i≠j}，其中di为顶节点的有效通信半径，d(vi，vj)为与pij关联的vi和vj之间的欧几里德距离。图G(V，E)的拓扑结构是由顶点集V的某种分布及d(vi，vj)≤min(di，dj)的限定决定的，为一种自然属性。

2.1 拓扑结构的特点

图2所示网络拓扑图是一简单图且是一个连通图，没有圈也没有重数大于1的边。对一个顶点集V={v0，v1，…，vm}，在选定 0 层顶点v0后，按E={pij|i=0，1，2，…，m;j=0，1，2，…，m;d(vi，vj)≤min(di，dj)，i≠j}中的条件构建pij，则任意顶点vi和vj间的通路u(vi，vj)将是它们间最短的无线信道。这样的通路为无线传感器网络的节能控制和通信跳数最少带来拓扑结构上的优势。图2所示网络拓扑结构是一个层次型的网络拓扑结构，如去掉图2中粗实线表示的同层顶点间的边，这个拓扑结构将蜕变为一个有R层顶点的多叉树拓扑结构［5］，0层顶点是根节点，r层顶点是(r-1)层顶点的根，(r-1)层顶点是(r-2)层顶点的根，顶点vi至v0的通路u(v0，vi)是唯一的。

定义p1ij为多叉树拓扑结构T{V，E1}的边，E1={p1ij|i=0，1，2，…，m;j=0，1，2，…，m;d(vi，vj)≤min(di，dj)，i≠j}。p2ij为同层顶点构成图F{V，E2}的边，E2={p2ij|i=0，1，2，…，m;j=0，1，2，…，m;d(vi，vj)≤min(di，dj)，i≠j}，则E可表示为{E1∪E2|E1∩E2=Φ}。树型拓扑结构的图是连通度最小的图［6］，树的边连通度与点连通度均为1，降低了两点间信道存在的可靠性，但同层顶点的边集E2增加了图G(V，E)的通路数，边集E2的边数是图G(V，E)的基本回路数，而图G(V，E)的回路数大于等于基本回路数，故图G(V，E)的连通性变好。由m个顶点构成的树T具有(m-1)条边，树是连通的，图G(V，E)是在0 层顶点选定后，按照{d(vi，vj)≤min(di，dj)，i≠j}构建pij形成的，因此多叉树T{V，E1}是图G(V，E)唯一的生成树。树的层数越少，则通路u(v0，vi)的长度k0i越小，即顶点vi至根顶点v0的无线信号传输的跳数越少。

2.2 顶点的特点

定义S(vi)⊂E，S(vi)为vi的关联集，0层顶点v0为割点，最后一层的各顶点vi为割点，中间各层顶点的S(vi)可能是割集，也可能不是割集。对应割集的顶点是拓扑结构中负担相对重一些、但必须存在的顶点。在图G(V，E)的所有割点中，除根顶点v0外，其他顶点均是不同层上的根顶点，r层顶点与(r-1)层顶点间的通路u(vi，vj)的长度kij为1，即无线通信跳数为1。因此，这样的树型层次结构使各顶点vi至根顶点v0间的信号传输总跳数将是该拓扑结构下最少的。

为了方便顶点的识别，定义IDS0(vi)为顶节点的唯一IDi号(节点数据接收0通道地址)，IDS1(vi)为顶节点的唯一IDi号(节点数据接收1通道地址)，IDF(vi)为顶节点的唯一IDi号(节点数据发送通道地址)。IDi∈(0，1，2，…，A)，A为最大无线模块信道地址。

2.3 树型层次结构网络的优点

若构建一个图2所示树型层次结构的无线传感器网络，则层次性符合传感器节点无线信号传输的单跳性，树型结构搜索的顺序性符合传感器节点位置的分布性和节点地址的唯一性［7］。在全网节点有效的情况下，用其生成树T{V，E1}进行路由选择，则路由唯一，全网络节点通信平均跳数最短，平均通信时间最短，平均耗能最少。这种树型层次结构的生成树T是自然选择，取决于节点通信半径。F{V，E2}的边集E2为生成树T{V，E1}提供了一跳的最短路由转移，用于有节点失效时的路由选择。

3 数据链路层

数据链路层负责数据成帧、帧检测、差错控制以及无线信道的使用控制，减少邻居节点广播引起的冲突［8］。本文以测温为应用背景，考虑数据的正确性与系统的性能要求，确定如下数据帧:第一个字节为节点状态与控制字节，其后五个字节为节点地址，第六、七个字节为节点所在层号，后两个字节为节点温度值的高8位与低8位，如图3所示。

图3 数据帧格式Fig.3 The data frame

第一个字节中各数据位(b0～b7)定义如下。

b0为电量状态位。

b1、b2和b3为节点数据传输状态与控制编码:000上行命令、001下行命令、010从动上行状态、011主动上行状态、100经同层其他节点上行状态、101校时命令、111等待状态。

b4和b5为本节点组网状态与控制编码:00未组网状态、01组网状态、10组网命令、11退网命令。

b6和b7为节点状态编码:00失效状态、01有效状态、10新节点入网状态。

温度传感器DS18B20高速暂存(便笺式RAM)中的第九个字节是前8个字节的CRC8校验码，所以处理器与温度传感器间数据传输的正确性由CRC8校验码来检验，其等效多项式函数为CRC=X8+X5+X4+1。nRF24L01芯片可选CRC8或CRC16校验码对所发数据自动进行硬件CRC校验，并在发送数据帧的最后加上该CRC校验码，以确保nRF24L01芯片之间数据收发的正确性。本设计选择CRC16校验。处理器与nRF24L01芯片之间通过SPI串行接口通信，数据收发的正确性有较高的保证。无线信道采用码分制，由5个字节进行地址分配，各节点共用同一个频道。

4 路由层设计

路由层实现数据融合，负责路由生成和路由选择［9］。本设计采用树型层次结构的路由协议，以树型结构形式构建各层节点集，根节点只有一个v0，为0层节点，负责与上位计算机通信及全网络的数据上传和下达。层次结构的无线传感器网络符合无线数据信号传输的自然物理属性，所以一种可行的组网过程就可解决路由的建立，并得到每个入网节点的路由特性数据和全网的结构参数。

4.1 节点的路由特性数据定义

设节点的路由特性数据为结构数据Si={Ai，Bi，Ci，Di，Ei［m］，Fi［n］，Hi［k］，Sij［p］，IDi}。其中，Ai为第i个节点所处的层次号，Bi为第i个节点数据传输状态与控制编码，Ci为第i个节点组网状态与控制编码，Di为第i个节点状态编码，Ei［m］为第i个节点m个上一层节点地址数据，Fi［n］为第i个节点n个下一层节点地址数据，Hi［k］为第i个节点k个同一层节点地址数据，Sij［p］为第i个节点第j条信道可通达的所有下层节点地址数据，IDi为第i个节点被分配的地址。节点在第一次上电后，以上数据的初值分别为:Bi=111，Di=01，其他全为0。将这些数据存入EEPROM中，并定义该节点未入网。

4.2 传感器节点收发地址配置

为了便于组网、保证正常的网络数据传输，将各节点数据接收1通道地址配置为1，用于组网;入网后，0通道地址配置为IDi，用于数据上下行传输。各节点无线模块发送地址首次都配置为最高层(0层)节点的接收通道地址，可接收上层的数据，入网后发送地址为其上层节点接收地址。本文提出的树型层次组网方式是一种受控的主动组网模式。由于广播每层组网信息时，在发送节点通信范围内可能存在多个可通信的节点，因此当它们在响应发送节点信息时，必存在无线数据拥挤与信道竞争现象［9］，极易导致通信失败。故在进行节点程序设计时做了如下考虑。若节点未组网，收到组网信息后，则定时器回零，重新定时。产生10遍3位的随机数后，再产生1遍随机数，此数值作为本节点响应发送节点信息的时刻。然后再产生5 B的随机数，将其作为本节点的数据接收0通道的地址IDi。定时时间到后，向其上层节点发送本节点的0通道地址及已组网状态，最终传至0层节点。0层节点根据收到的下层节点0通道随机数地址IDi的前后次序，重新分配各下层节点0通道的地址IDi∈(0，1，…，65 535)。从而使得响应节点发生通信冲突的可能性大为减少。

4.3 组网算法

一个节点的组网算法应具有组网与被组网的功能，即一个节点一般有上层节点和下层节点。

4.3.1 上层节点组网算法

上层节点组网算法具体如下。

①层节点发送第一层的组网信息(r=1)。

②等待数据接收中断信号。当有中断信号时，转步骤③;否则，转步骤④。

③接收上传的路由特性数据。当有延时后上传的路由特性数据时，转步骤②。

④层节点等待一段时间后，若一次或连续两次未收到上传数据，可能是无线信号偶尔丢失，返步骤①;若连续3次未收到上传数据，则认为第1层组网结束，重新配置新入网节点IDi，令r=r+1，转步骤⑤。

⑤ 层节点按F0［n］中所记IDi的次序，依次令第j个信道(已入网节点)发第r层的组网信息，其中r∈(2，3，…，R)。S0j［p］记录第j信道上所有下层节点的IDi。

⑥等待数据接收中断信号。若有中断信号，则转步骤⑦;否则，转步骤⑧。

⑦接收上传的路由特性数据。当有延时后上传的路由特性数据时，转步骤⑥。

⑧层节点等待一段时间后，若一次或连续两次未收到上传数据，可能是无线信号偶尔丢失，则r不变，j不变，返步骤⑤;若连续3次未收到上传数据，则认为某个联通信道第r层组网结束，重新配置新入网节点IDi。判断有无未用信道，有则r不变并返步骤⑤;无则第r层组网结束。

⑨若信道j遍历完后未有一次数据上传，则全网组网结束;否则r=r+1并返步骤⑤。

4.3.2 下层节点组网算法

下层节点组网算法具体如下。

①如某个节点i收到组网信息，判断本节点是否已入网，若已入网，则转步骤④;否则转步骤②。

②Ai=r、Bi=111、Ci=01、Di=01，配置节点i的数据接收0通道地址为IDi，发送地址为上层数据接收通道地址，上传本节点数据帧，记父节点IDi于Ei［k］中。

③逐层上传第i个节点的路由特性数据，并逐层记录。0层节点记入第j个信道的下层节点地址数据池S0j［p］中，(r-1)层的中继节点x记入Fx［n］、Sxj［p］中，其他层的中继节点x记入Sxj［p］中。

④若组网信息中的层次号比本节点的层次号大1，则两节点为同层节点，记IDi于Hi［k］中;否则转步骤⑤。

⑤本节点为(r-1)层已入网节点，负责该节点下的第r层节点的组网。每组网一个r层节点，则上传一个路由特性数据，直至组网完成该节点下的所有r层节点。

5 特性数据与路由协议

上述树型层次结构的组网算法可使各层节点具有若干条信道，同层次节点间可能也相互存在信道，所以某个节点数据的上下行的路径可能是不唯一的，这提高了网络的连通性。由组网算法可知，这是有序的组网，其由0层节点发出组网指令，组网结束后，上位计算机就可以获得各个入网节点的路由特性数据，从而了解全网络的网络结构和所有可能路由，为网络的管理使用提供依据。

5.1 节点通信跳数

节点分布确定后，一旦0层节点位置选定，则本组网算法下的无线传感器网络的结构也就确定了。在组网过程中，组网信息的发布是广播式的，即从0层节点所在位置逐渐向通信远点扩展，故相邻层之间的通信是一跳。无失效节点时，由Ei［m］和Fi［n］选择的路由将是通信跳数最少的;有失效节点时，由Ei［m］和Fi［n］及Hi［k］选择的路由也将是该情况下通信跳数最少的。该网络通信跳数最少的优点得益于广播式树型层次组网方式的自然属性。

5.2 节点分布位置估算

每个节点均有层次号r，设节点通信距离为d，r×d约为该节点距0层节点的直线距离DISi。由节点路由特性数据可得到从0层节点联通到该节点的最短路由Li，如能确定Li之间左、中、右的方位关系，可在Li中选定一个参考，用极坐标的两维关系来表达节点的位置。这时Li相当于幅角，DISi相当于幅值。但实际中Li之间左、中、右的定量方位关系难以确定。可利用已建无线网络的所有可能信道和该网络已有节点路由特性数据，近似推算出Li间的定量方位关系。

5.3 树型层次结构路由协议

路由层协议如下:下行时，发送节点根据目标节点地址，在发送节点的Sij［p］中搜索该目标节点地址，确定或选择发送节点至下一层的信道。发送节点至下一层的信道存放在发送节点下行路由Fi［n］中，可均衡选择，以达到对电池能量的均衡消耗。逐层下行数据，逐层均衡选择可用信道，直至数据传到目标节点。上行时，由于本网络的上行目标节点就是0层节点，因此发送节点在其上行路由Ei［m］中确定或选择发送至上一层的信道，并逐层上行数据，逐层均衡选择可用信道，直至数据传到目标节点。在数据上下行的过程中，若发送节点的Ei［m］或Fi［k］路由失效，可在其Hi［k］中确定或选择信道，以传送上下行数据。

5.4 数据传输丢包处理

在无线数据传输过程中，丢包现象经常发生，环境参数的变化、电源参数的波动、信号参数受到干扰等都会导致丢包现象。但丢包问题必须解决，否则就相当于路由不通。本文利用nRF24L01硬件的自动应答与重发功能，设定5次点到点之间的自动应答与重发。若5次应答与重发都不成功，则发送节点选择其他可能路径，并根据该节点失效的次数决定选择上传该节点失效的信息。

6 树型层次结构路由算法

路由算法是具体实现路由协议的一种思路与方法，是数据传输程序设计的一种逻辑结构［10］，决定了目标程序的正确性、可靠性、容错性、通用性和灵活性。

6.1 基本路由算法

路由算法作用于节点进行数据上下行传输的控制程序中，是数据传输程序的一部分。基本路由算法如下。

① 发送节点在Fi［n］或Ei［m］中计算可用信道，选定一信道，发送数据包。

②若所选信道成功接收，则转步骤⑤，否则转步骤③。

③ 在Fi［n］或Ei［m］及Hi［k］中计算信道，如有可选信道，则发送数据包，转步骤②;如无信道可选，转步骤④。

④如是发送节点主动发送数据，则失败;否则向该节点的发送方发送数据传输失败信息。

⑤节点配置为接收状态，等待处理节点事务。

6.2 数据传输失败路由算法

数据传输失败路由算法具体如下。

①收到数据传输失败信息。

②判断是上行失败还是下行失败，若是下行失败，则选择Fi［n］计算另一个可用信道;若是上行失败，则选择Ei［m］和Hi［k］计算另一个可用信道。

③如存在另一个可用信道，则发送数据，并转步骤⑥;如不存在，则转步骤④。

④判断本节点是否为原发送节点，若是，则发送失败，转步骤⑥，否则转步骤⑤。

⑤查找到最近一次转发数据所用的信道，发送数据传输失败信息。

⑥节点配置为接收状态，等待处理节点事务。

6.3 新节点入网算法

在本系统中，新节点入网要解决的问题是新节点在该网络中的网络位置是中间节点还是终节点，网络层次号是什么。新节点入网算法具体如下。

①广播入网信息，要求响应节点的0通道地址IDi。

② 如有不同0通道地址IDi，则记入Ei［m］中，并上传新节点的0通道地址IDi，转步骤①，否则转步骤③。

③ 分析Ei［m］，如有层次号差大于2的，本节点层次号取其中间的一个数;否则任取已知层次号中的一个，转步骤④;如无数据，则入网失败。

④上传新节点路由特性数据。

⑤配置无线模块为接收状态，等待处理节点事务。

7 结束语

本文采用31个节点组成了一个无线传感器网络测温系统并进行了测试，其中1个节点作为0层节点，负责与上位计算机通信，其他30个节点构成5层树型层次结构网络。该网络能成功组网，数据上下行正常。网络的工作方式主要为网络节点主动上传数据。由0层节点每隔一定时间(如90 min)向全网发送一次校时信号，使全网节点时间同步。每个节点隔5 min上传一次数据，各节点第一次上传数据的时刻可由该节点0通道地址数据(0～65 535)加3得到，单位为秒(3为各节点之间的发送间隔即3 s)。本文提出的时间驱动工作方式不会出现无线信道拥挤的现象，节省了处理信道拥挤的开销和信息传输时间。该树型层次结构网络通信速度快，可均衡使用信道，路由明晰，有较好的网络连通性;路由算法具有一定的键壮性，较好地保证了该网络的可靠性与可用性，易于工程实现。

［1］张学.无线传感器网络的拓扑控制［J］.软件学报，2007，18(4):945.

［2］李建中，高宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45(1):5.

［3］ Intanagonwiwat C.A scalable and robust communication paradigm for sensor networks［C］//Directed Diffusion，Proceedings of the Sixth Annual International Conference on Mobile Computing and Networks(MobiCom 2000)，Boston，2000:56-67.

［4］ 任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2004，14(7):1283.

［5］王树禾.数学模型基础［M］.合肥:中国科学技术大学出版社，1996:178.

［6］王朝瑞.图论［M］.北京:北京理工大学出版社，1987:236.

［7］ Raghavendra C，Sivalingam K，Zhati T，et al.Wireless sensor networks［M］.Kluwer Academic Publishers，2004:190.

［8］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005:156.

［9］缪强，郑扣根.无线传感器网络的路由协议设计研究［J］.计算机应用研究，2004(3):35.

［10］Bars S.计算机算法设计和分析引论［M］.上海:复旦大学出版社，1985:48.

Application Study of the Wireless Sensor Network with Tree Hierarchical Structure

In accordance with the topological structure of wireless sensor network，the tree type hierarchical structure for wireless sensor network is proposed.With this structure，data transmission can be conducted using least of hops and the energy of the node batteries can be equally used.In addition，the estimating method of node locations and the solution for data packet loss are given.The route algorithm of the network is designed and verified.This wireless sensors network features maturity of the technology，low cost，easy to project implementation，and better practical application value，the network structure possesses certain versatility.

Wireless sensor network Sensor node Network topological structure Algorithm Route

TP393

A

修改稿收到日期:2012-05-25。

作者于标(1962-)，男，1983年毕业于山东科技大学电气自动化专业，获硕士学位，副教授;主要从事无线传感器网络技术、微机测控技术、自动控制理论与应用的研究。