于 標(biāo)

(揚(yáng)州市職業(yè)大學(xué)電氣與汽車工程學(xué)院，江蘇 揚(yáng)州 225009)

一種樹型層次結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)應(yīng)用研究

于 標(biāo)

(揚(yáng)州市職業(yè)大學(xué)電氣與汽車工程學(xué)院，江蘇 揚(yáng)州 225009)

針對無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，提出了一種樹型層次結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)。該網(wǎng)絡(luò)結(jié)構(gòu)可用最少的無線通信跳數(shù)進(jìn)行數(shù)據(jù)傳輸，能均衡使用節(jié)點(diǎn)電池能量。同時(shí)給出了節(jié)點(diǎn)位置估算法和數(shù)據(jù)丟包解決法，設(shè)計(jì)并驗(yàn)證了該網(wǎng)絡(luò)的路由算法。該無線傳感器網(wǎng)絡(luò)所用技術(shù)成熟、成本低、易于工程實(shí)現(xiàn)，具有較好的實(shí)用價(jià)值，其網(wǎng)絡(luò)結(jié)構(gòu)具有一定的通用性。

無線傳感器網(wǎng)絡(luò) 傳感器節(jié)點(diǎn) 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 算法 路由

0 引言

根據(jù)節(jié)點(diǎn)是否移動(dòng)和節(jié)點(diǎn)的布置是否可控，無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可分為4類來構(gòu)建。目前，拓?fù)浣Y(jié)構(gòu)的控制研究已經(jīng)形成功率控制和睡眠調(diào)度兩個(gè)主流研究方向［1］。在保證一定的網(wǎng)絡(luò)連通質(zhì)量和覆蓋質(zhì)量的前提下，一般以延長網(wǎng)絡(luò)的生命周期為主要目標(biāo)，兼顧通信干擾、網(wǎng)絡(luò)延遲、負(fù)載均衡、簡單性、可靠性和可擴(kuò)展性等性能，形成一個(gè)優(yōu)化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［2］。

已公開報(bào)道的各無線傳感器網(wǎng)絡(luò)路由協(xié)議都有一定的條件設(shè)定和局限性。簡單的路由協(xié)議有洪泛協(xié)議、惡劣環(huán)境中的可靠路由算法、定向擴(kuò)散協(xié)議［3］。無線傳感器網(wǎng)絡(luò)路由的建立和選擇與組網(wǎng)密切相關(guān)，組網(wǎng)過程決定了所有可能的路由路徑。因此，在一個(gè)主節(jié)點(diǎn)的控制下進(jìn)行有序的組網(wǎng)是一種實(shí)用有效的解決方法。

1 無線傳感器節(jié)點(diǎn)

無線傳感器節(jié)點(diǎn)中的無線模塊和處理器模塊對組網(wǎng)起關(guān)鍵性的作用，兩者決定了節(jié)點(diǎn)的通信性能和數(shù)據(jù)處理能力［4］。過于低廉的功能芯片不可能獲得優(yōu)良的通信性能和數(shù)據(jù)處理能力。本文設(shè)計(jì)和使用的測溫?zé)o線傳感器節(jié)點(diǎn)電路圖如圖1所示，其性能穩(wěn)定，工作可靠。其中Address為地址選擇電路。

圖1 節(jié)點(diǎn)電路圖Fig.1 The node circuit

無線模塊選擇了北京迅通科技有限公司基于nRF24L01的產(chǎn)品，通信范圍在 30～40 m左右。nRF24L01是一款工作在2.4～2.5 GHz的單片無線收發(fā)器芯片，有125個(gè)工作頻道，每個(gè)頻道有40 bit的地址選擇，具有功耗低、硬件自動(dòng)應(yīng)答與重發(fā)功能、價(jià)格低等特點(diǎn)。處理器選擇ATMEL公司的Atmega8L單片機(jī)。Atmega8L單片機(jī)有512 B的EEPROM和8 kB的可編程Flash，提供1種工作模式和5種睡眠模式，其SPI硬件接口可與nRF24L01直接相聯(lián)，是一款低功耗、高性能、性價(jià)比較好的單片機(jī)。電池選擇一節(jié)7號1.2 V、900 mA的可充電電池。系統(tǒng)采用BL8550/5.0升壓芯片將電源電壓升至5 V，供DS18B20使用;采用TPS76333電源管理芯片將5 V電壓轉(zhuǎn)變?yōu)?.3 V電壓，供Atmega8L和nRF24L01使用。上述兩個(gè)電源芯片都具有穩(wěn)壓性能。

2 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

一個(gè)無線傳感器網(wǎng)絡(luò)的布置總是有具體的應(yīng)用目標(biāo)，各節(jié)點(diǎn)的位置一般也非隨意安排，由均勻布置、信號有效范圍相互覆蓋等要求來定位。節(jié)點(diǎn)的物理屬性確定了各節(jié)點(diǎn)間的信號是否能通達(dá)，故頂點(diǎn)集V={v0，v1，…，vm}必存在一個(gè)邊數(shù)最多的拓?fù)浣Y(jié)構(gòu)Gmax(V，Emax)，其中，Emax?V＆V，為無序積(V＆V)的一個(gè)子集。成功的節(jié)點(diǎn)布置會(huì)使Emax的關(guān)聯(lián)包含頂點(diǎn)集V的所有元素，則該拓?fù)浣Y(jié)構(gòu)是連通的，但不一定是較易控制和管理的網(wǎng)絡(luò)結(jié)構(gòu)。由Gmax(V，Emax)可生成不同的子圖G(V，E)，其中E?Emax。E的選擇決定了無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)屬性和網(wǎng)絡(luò)能力。樹型層次結(jié)構(gòu)網(wǎng)絡(luò)拓?fù)鋱D如圖2所示。

圖2 樹型層次結(jié)構(gòu)網(wǎng)絡(luò)拓?fù)鋱DFig.2 Topology of tree hierachical network

定義圖2的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為圖G(V，E)。其中，V={v0，v1，…，vm}，頂點(diǎn)vi和vj之間只有一條邊pij相聯(lián)。從信號能通達(dá)的角度來看，兩個(gè)無線節(jié)點(diǎn)之間只有一種關(guān)聯(lián)。E={pij|i=0，1，2，…，m;j=0，1，2，…，m;d(vi，vj)≤min(di，dj)，i≠j}，其中di為頂節(jié)點(diǎn)的有效通信半徑，d(vi，vj)為與pij關(guān)聯(lián)的vi和vj之間的歐幾里德距離。圖G(V，E)的拓?fù)浣Y(jié)構(gòu)是由頂點(diǎn)集V的某種分布及d(vi，vj)≤min(di，dj)的限定決定的，為一種自然屬性。

2.1 拓?fù)浣Y(jié)構(gòu)的特點(diǎn)

圖2所示網(wǎng)絡(luò)拓?fù)鋱D是一簡單圖且是一個(gè)連通圖，沒有圈也沒有重?cái)?shù)大于1的邊。對一個(gè)頂點(diǎn)集V={v0，v1，…，vm}，在選定 0 層頂點(diǎn)v0后，按E={pij|i=0，1，2，…，m;j=0，1，2，…，m;d(vi，vj)≤min(di，dj)，i≠j}中的條件構(gòu)建pij，則任意頂點(diǎn)vi和vj間的通路u(vi，vj)將是它們間最短的無線信道。這樣的通路為無線傳感器網(wǎng)絡(luò)的節(jié)能控制和通信跳數(shù)最少帶來拓?fù)浣Y(jié)構(gòu)上的優(yōu)勢。圖2所示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一個(gè)層次型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如去掉圖2中粗實(shí)線表示的同層頂點(diǎn)間的邊，這個(gè)拓?fù)浣Y(jié)構(gòu)將蛻變?yōu)橐粋€(gè)有R層頂點(diǎn)的多叉樹拓?fù)浣Y(jié)構(gòu)［5］，0層頂點(diǎn)是根節(jié)點(diǎn)，r層頂點(diǎn)是(r-1)層頂點(diǎn)的根，(r-1)層頂點(diǎn)是(r-2)層頂點(diǎn)的根，頂點(diǎn)vi至v0的通路u(v0，vi)是唯一的。

定義p1ij為多叉樹拓?fù)浣Y(jié)構(gòu)T{V，E1}的邊，E1={p1ij|i=0，1，2，…，m;j=0，1，2，…，m;d(vi，vj)≤min(di，dj)，i≠j}。p2ij為同層頂點(diǎn)構(gòu)成圖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=Φ}。樹型拓?fù)浣Y(jié)構(gòu)的圖是連通度最小的圖［6］，樹的邊連通度與點(diǎn)連通度均為1，降低了兩點(diǎn)間信道存在的可靠性，但同層頂點(diǎn)的邊集E2增加了圖G(V，E)的通路數(shù)，邊集E2的邊數(shù)是圖G(V，E)的基本回路數(shù)，而圖G(V，E)的回路數(shù)大于等于基本回路數(shù)，故圖G(V，E)的連通性變好。由m個(gè)頂點(diǎn)構(gòu)成的樹T具有(m-1)條邊，樹是連通的，圖G(V，E)是在0 層頂點(diǎn)選定后，按照{(diào)d(vi，vj)≤min(di，dj)，i≠j}構(gòu)建pij形成的，因此多叉樹T{V，E1}是圖G(V，E)唯一的生成樹。樹的層數(shù)越少，則通路u(v0，vi)的長度k0i越小，即頂點(diǎn)vi至根頂點(diǎn)v0的無線信號傳輸?shù)奶鴶?shù)越少。

2.2 頂點(diǎn)的特點(diǎn)

定義S(vi)?E，S(vi)為vi的關(guān)聯(lián)集，0層頂點(diǎn)v0為割點(diǎn)，最后一層的各頂點(diǎn)vi為割點(diǎn)，中間各層頂點(diǎn)的S(vi)可能是割集，也可能不是割集。對應(yīng)割集的頂點(diǎn)是拓?fù)浣Y(jié)構(gòu)中負(fù)擔(dān)相對重一些、但必須存在的頂點(diǎn)。在圖G(V，E)的所有割點(diǎn)中，除根頂點(diǎn)v0外，其他頂點(diǎn)均是不同層上的根頂點(diǎn)，r層頂點(diǎn)與(r-1)層頂點(diǎn)間的通路u(vi，vj)的長度kij為1，即無線通信跳數(shù)為1。因此，這樣的樹型層次結(jié)構(gòu)使各頂點(diǎn)vi至根頂點(diǎn)v0間的信號傳輸總跳數(shù)將是該拓?fù)浣Y(jié)構(gòu)下最少的。

為了方便頂點(diǎn)的識(shí)別，定義IDS0(vi)為頂節(jié)點(diǎn)的唯一IDi號(節(jié)點(diǎn)數(shù)據(jù)接收0通道地址)，IDS1(vi)為頂節(jié)點(diǎn)的唯一IDi號(節(jié)點(diǎn)數(shù)據(jù)接收1通道地址)，IDF(vi)為頂節(jié)點(diǎn)的唯一IDi號(節(jié)點(diǎn)數(shù)據(jù)發(fā)送通道地址)。IDi∈(0，1，2，…，A)，A為最大無線模塊信道地址。

2.3 樹型層次結(jié)構(gòu)網(wǎng)絡(luò)的優(yōu)點(diǎn)

若構(gòu)建一個(gè)圖2所示樹型層次結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)，則層次性符合傳感器節(jié)點(diǎn)無線信號傳輸?shù)膯翁?，樹型結(jié)構(gòu)搜索的順序性符合傳感器節(jié)點(diǎn)位置的分布性和節(jié)點(diǎn)地址的唯一性［7］。在全網(wǎng)節(jié)點(diǎn)有效的情況下，用其生成樹T{V，E1}進(jìn)行路由選擇，則路由唯一，全網(wǎng)絡(luò)節(jié)點(diǎn)通信平均跳數(shù)最短，平均通信時(shí)間最短，平均耗能最少。這種樹型層次結(jié)構(gòu)的生成樹T是自然選擇，取決于節(jié)點(diǎn)通信半徑。F{V，E2}的邊集E2為生成樹T{V，E1}提供了一跳的最短路由轉(zhuǎn)移，用于有節(jié)點(diǎn)失效時(shí)的路由選擇。

3 數(shù)據(jù)鏈路層

數(shù)據(jù)鏈路層負(fù)責(zé)數(shù)據(jù)成幀、幀檢測、差錯(cuò)控制以及無線信道的使用控制，減少鄰居節(jié)點(diǎn)廣播引起的沖突［8］。本文以測溫為應(yīng)用背景，考慮數(shù)據(jù)的正確性與系統(tǒng)的性能要求，確定如下數(shù)據(jù)幀:第一個(gè)字節(jié)為節(jié)點(diǎn)狀態(tài)與控制字節(jié)，其后五個(gè)字節(jié)為節(jié)點(diǎn)地址，第六、七個(gè)字節(jié)為節(jié)點(diǎn)所在層號，后兩個(gè)字節(jié)為節(jié)點(diǎn)溫度值的高8位與低8位，如圖3所示。

圖3 數(shù)據(jù)幀格式Fig.3 The data frame

第一個(gè)字節(jié)中各數(shù)據(jù)位(b0～b7)定義如下。

b0為電量狀態(tài)位。

b1、b2和b3為節(jié)點(diǎn)數(shù)據(jù)傳輸狀態(tài)與控制編碼:000上行命令、001下行命令、010從動(dòng)上行狀態(tài)、011主動(dòng)上行狀態(tài)、100經(jīng)同層其他節(jié)點(diǎn)上行狀態(tài)、101校時(shí)命令、111等待狀態(tài)。

b4和b5為本節(jié)點(diǎn)組網(wǎng)狀態(tài)與控制編碼:00未組網(wǎng)狀態(tài)、01組網(wǎng)狀態(tài)、10組網(wǎng)命令、11退網(wǎng)命令。

b6和b7為節(jié)點(diǎn)狀態(tài)編碼:00失效狀態(tài)、01有效狀態(tài)、10新節(jié)點(diǎn)入網(wǎng)狀態(tài)。

溫度傳感器DS18B20高速暫存(便箋式RAM)中的第九個(gè)字節(jié)是前8個(gè)字節(jié)的CRC8校驗(yàn)碼，所以處理器與溫度傳感器間數(shù)據(jù)傳輸?shù)恼_性由CRC8校驗(yàn)碼來檢驗(yàn)，其等效多項(xiàng)式函數(shù)為CRC=X8+X5+X4+1。nRF24L01芯片可選CRC8或CRC16校驗(yàn)碼對所發(fā)數(shù)據(jù)自動(dòng)進(jìn)行硬件CRC校驗(yàn)，并在發(fā)送數(shù)據(jù)幀的最后加上該CRC校驗(yàn)碼，以確保nRF24L01芯片之間數(shù)據(jù)收發(fā)的正確性。本設(shè)計(jì)選擇CRC16校驗(yàn)。處理器與nRF24L01芯片之間通過SPI串行接口通信，數(shù)據(jù)收發(fā)的正確性有較高的保證。無線信道采用碼分制，由5個(gè)字節(jié)進(jìn)行地址分配，各節(jié)點(diǎn)共用同一個(gè)頻道。

4 路由層設(shè)計(jì)

路由層實(shí)現(xiàn)數(shù)據(jù)融合，負(fù)責(zé)路由生成和路由選擇［9］。本設(shè)計(jì)采用樹型層次結(jié)構(gòu)的路由協(xié)議，以樹型結(jié)構(gòu)形式構(gòu)建各層節(jié)點(diǎn)集，根節(jié)點(diǎn)只有一個(gè)v0，為0層節(jié)點(diǎn)，負(fù)責(zé)與上位計(jì)算機(jī)通信及全網(wǎng)絡(luò)的數(shù)據(jù)上傳和下達(dá)。層次結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)符合無線數(shù)據(jù)信號傳輸?shù)淖匀晃锢韺傩裕砸环N可行的組網(wǎng)過程就可解決路由的建立，并得到每個(gè)入網(wǎng)節(jié)點(diǎn)的路由特性數(shù)據(jù)和全網(wǎng)的結(jié)構(gòu)參數(shù)。

4.1 節(jié)點(diǎn)的路由特性數(shù)據(jù)定義

設(shè)節(jié)點(diǎn)的路由特性數(shù)據(jù)為結(jié)構(gòu)數(shù)據(jù)Si={Ai，Bi，Ci，Di，Ei［m］，F(xiàn)i［n］，Hi［k］，Sij［p］，IDi}。其中，Ai為第i個(gè)節(jié)點(diǎn)所處的層次號，Bi為第i個(gè)節(jié)點(diǎn)數(shù)據(jù)傳輸狀態(tài)與控制編碼，Ci為第i個(gè)節(jié)點(diǎn)組網(wǎng)狀態(tài)與控制編碼，Di為第i個(gè)節(jié)點(diǎn)狀態(tài)編碼，Ei［m］為第i個(gè)節(jié)點(diǎn)m個(gè)上一層節(jié)點(diǎn)地址數(shù)據(jù)，F(xiàn)i［n］為第i個(gè)節(jié)點(diǎn)n個(gè)下一層節(jié)點(diǎn)地址數(shù)據(jù)，Hi［k］為第i個(gè)節(jié)點(diǎn)k個(gè)同一層節(jié)點(diǎn)地址數(shù)據(jù)，Sij［p］為第i個(gè)節(jié)點(diǎn)第j條信道可通達(dá)的所有下層節(jié)點(diǎn)地址數(shù)據(jù)，IDi為第i個(gè)節(jié)點(diǎn)被分配的地址。節(jié)點(diǎn)在第一次上電后，以上數(shù)據(jù)的初值分別為:Bi=111，Di=01，其他全為0。將這些數(shù)據(jù)存入EEPROM中，并定義該節(jié)點(diǎn)未入網(wǎng)。

4.2 傳感器節(jié)點(diǎn)收發(fā)地址配置

為了便于組網(wǎng)、保證正常的網(wǎng)絡(luò)數(shù)據(jù)傳輸，將各節(jié)點(diǎn)數(shù)據(jù)接收1通道地址配置為1，用于組網(wǎng);入網(wǎng)后，0通道地址配置為IDi，用于數(shù)據(jù)上下行傳輸。各節(jié)點(diǎn)無線模塊發(fā)送地址首次都配置為最高層(0層)節(jié)點(diǎn)的接收通道地址，可接收上層的數(shù)據(jù)，入網(wǎng)后發(fā)送地址為其上層節(jié)點(diǎn)接收地址。本文提出的樹型層次組網(wǎng)方式是一種受控的主動(dòng)組網(wǎng)模式。由于廣播每層組網(wǎng)信息時(shí)，在發(fā)送節(jié)點(diǎn)通信范圍內(nèi)可能存在多個(gè)可通信的節(jié)點(diǎn)，因此當(dāng)它們在響應(yīng)發(fā)送節(jié)點(diǎn)信息時(shí)，必存在無線數(shù)據(jù)擁擠與信道競爭現(xiàn)象［9］，極易導(dǎo)致通信失敗。故在進(jìn)行節(jié)點(diǎn)程序設(shè)計(jì)時(shí)做了如下考慮。若節(jié)點(diǎn)未組網(wǎng)，收到組網(wǎng)信息后，則定時(shí)器回零，重新定時(shí)。產(chǎn)生10遍3位的隨機(jī)數(shù)后，再產(chǎn)生1遍隨機(jī)數(shù)，此數(shù)值作為本節(jié)點(diǎn)響應(yīng)發(fā)送節(jié)點(diǎn)信息的時(shí)刻。然后再產(chǎn)生5 B的隨機(jī)數(shù)，將其作為本節(jié)點(diǎn)的數(shù)據(jù)接收0通道的地址IDi。定時(shí)時(shí)間到后，向其上層節(jié)點(diǎn)發(fā)送本節(jié)點(diǎn)的0通道地址及已組網(wǎng)狀態(tài)，最終傳至0層節(jié)點(diǎn)。0層節(jié)點(diǎn)根據(jù)收到的下層節(jié)點(diǎn)0通道隨機(jī)數(shù)地址IDi的前后次序，重新分配各下層節(jié)點(diǎn)0通道的地址IDi∈(0，1，…，65 535)。從而使得響應(yīng)節(jié)點(diǎn)發(fā)生通信沖突的可能性大為減少。

4.3 組網(wǎng)算法

一個(gè)節(jié)點(diǎn)的組網(wǎng)算法應(yīng)具有組網(wǎng)與被組網(wǎng)的功能，即一個(gè)節(jié)點(diǎn)一般有上層節(jié)點(diǎn)和下層節(jié)點(diǎn)。

4.3.1 上層節(jié)點(diǎn)組網(wǎng)算法

上層節(jié)點(diǎn)組網(wǎng)算法具體如下。

①層節(jié)點(diǎn)發(fā)送第一層的組網(wǎng)信息(r=1)。

②等待數(shù)據(jù)接收中斷信號。當(dāng)有中斷信號時(shí)，轉(zhuǎn)步驟③;否則，轉(zhuǎn)步驟④。

③接收上傳的路由特性數(shù)據(jù)。當(dāng)有延時(shí)后上傳的路由特性數(shù)據(jù)時(shí)，轉(zhuǎn)步驟②。

④層節(jié)點(diǎn)等待一段時(shí)間后，若一次或連續(xù)兩次未收到上傳數(shù)據(jù)，可能是無線信號偶爾丟失，返步驟①;若連續(xù)3次未收到上傳數(shù)據(jù)，則認(rèn)為第1層組網(wǎng)結(jié)束，重新配置新入網(wǎng)節(jié)點(diǎn)IDi，令r=r+1，轉(zhuǎn)步驟⑤。

⑤ 層節(jié)點(diǎn)按F0［n］中所記IDi的次序，依次令第j個(gè)信道(已入網(wǎng)節(jié)點(diǎn))發(fā)第r層的組網(wǎng)信息，其中r∈(2，3，…，R)。S0j［p］記錄第j信道上所有下層節(jié)點(diǎn)的IDi。

⑥等待數(shù)據(jù)接收中斷信號。若有中斷信號，則轉(zhuǎn)步驟⑦;否則，轉(zhuǎn)步驟⑧。

⑦接收上傳的路由特性數(shù)據(jù)。當(dāng)有延時(shí)后上傳的路由特性數(shù)據(jù)時(shí)，轉(zhuǎn)步驟⑥。

⑧層節(jié)點(diǎn)等待一段時(shí)間后，若一次或連續(xù)兩次未收到上傳數(shù)據(jù)，可能是無線信號偶爾丟失，則r不變，j不變，返步驟⑤;若連續(xù)3次未收到上傳數(shù)據(jù)，則認(rèn)為某個(gè)聯(lián)通信道第r層組網(wǎng)結(jié)束，重新配置新入網(wǎng)節(jié)點(diǎn)IDi。判斷有無未用信道，有則r不變并返步驟⑤;無則第r層組網(wǎng)結(jié)束。

⑨若信道j遍歷完后未有一次數(shù)據(jù)上傳，則全網(wǎng)組網(wǎng)結(jié)束;否則r=r+1并返步驟⑤。

4.3.2 下層節(jié)點(diǎn)組網(wǎng)算法

下層節(jié)點(diǎn)組網(wǎng)算法具體如下。

①如某個(gè)節(jié)點(diǎn)i收到組網(wǎng)信息，判斷本節(jié)點(diǎn)是否已入網(wǎng)，若已入網(wǎng)，則轉(zhuǎn)步驟④;否則轉(zhuǎn)步驟②。

②Ai=r、Bi=111、Ci=01、Di=01，配置節(jié)點(diǎn)i的數(shù)據(jù)接收0通道地址為IDi，發(fā)送地址為上層數(shù)據(jù)接收通道地址，上傳本節(jié)點(diǎn)數(shù)據(jù)幀，記父節(jié)點(diǎn)IDi于Ei［k］中。

③逐層上傳第i個(gè)節(jié)點(diǎn)的路由特性數(shù)據(jù)，并逐層記錄。0層節(jié)點(diǎn)記入第j個(gè)信道的下層節(jié)點(diǎn)地址數(shù)據(jù)池S0j［p］中，(r-1)層的中繼節(jié)點(diǎn)x記入Fx［n］、Sxj［p］中，其他層的中繼節(jié)點(diǎn)x記入Sxj［p］中。

④若組網(wǎng)信息中的層次號比本節(jié)點(diǎn)的層次號大1，則兩節(jié)點(diǎn)為同層節(jié)點(diǎn)，記IDi于Hi［k］中;否則轉(zhuǎn)步驟⑤。

⑤本節(jié)點(diǎn)為(r-1)層已入網(wǎng)節(jié)點(diǎn)，負(fù)責(zé)該節(jié)點(diǎn)下的第r層節(jié)點(diǎn)的組網(wǎng)。每組網(wǎng)一個(gè)r層節(jié)點(diǎn)，則上傳一個(gè)路由特性數(shù)據(jù)，直至組網(wǎng)完成該節(jié)點(diǎn)下的所有r層節(jié)點(diǎn)。

5 特性數(shù)據(jù)與路由協(xié)議

上述樹型層次結(jié)構(gòu)的組網(wǎng)算法可使各層節(jié)點(diǎn)具有若干條信道，同層次節(jié)點(diǎn)間可能也相互存在信道，所以某個(gè)節(jié)點(diǎn)數(shù)據(jù)的上下行的路徑可能是不唯一的，這提高了網(wǎng)絡(luò)的連通性。由組網(wǎng)算法可知，這是有序的組網(wǎng)，其由0層節(jié)點(diǎn)發(fā)出組網(wǎng)指令，組網(wǎng)結(jié)束后，上位計(jì)算機(jī)就可以獲得各個(gè)入網(wǎng)節(jié)點(diǎn)的路由特性數(shù)據(jù)，從而了解全網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)和所有可能路由，為網(wǎng)絡(luò)的管理使用提供依據(jù)。

5.1 節(jié)點(diǎn)通信跳數(shù)

節(jié)點(diǎn)分布確定后，一旦0層節(jié)點(diǎn)位置選定，則本組網(wǎng)算法下的無線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)也就確定了。在組網(wǎng)過程中，組網(wǎng)信息的發(fā)布是廣播式的，即從0層節(jié)點(diǎn)所在位置逐漸向通信遠(yuǎn)點(diǎn)擴(kuò)展，故相鄰層之間的通信是一跳。無失效節(jié)點(diǎn)時(shí)，由Ei［m］和Fi［n］選擇的路由將是通信跳數(shù)最少的;有失效節(jié)點(diǎn)時(shí)，由Ei［m］和Fi［n］及Hi［k］選擇的路由也將是該情況下通信跳數(shù)最少的。該網(wǎng)絡(luò)通信跳數(shù)最少的優(yōu)點(diǎn)得益于廣播式樹型層次組網(wǎng)方式的自然屬性。

5.2 節(jié)點(diǎn)分布位置估算

每個(gè)節(jié)點(diǎn)均有層次號r，設(shè)節(jié)點(diǎn)通信距離為d，r×d約為該節(jié)點(diǎn)距0層節(jié)點(diǎn)的直線距離DISi。由節(jié)點(diǎn)路由特性數(shù)據(jù)可得到從0層節(jié)點(diǎn)聯(lián)通到該節(jié)點(diǎn)的最短路由Li，如能確定Li之間左、中、右的方位關(guān)系，可在Li中選定一個(gè)參考，用極坐標(biāo)的兩維關(guān)系來表達(dá)節(jié)點(diǎn)的位置。這時(shí)Li相當(dāng)于幅角，DISi相當(dāng)于幅值。但實(shí)際中Li之間左、中、右的定量方位關(guān)系難以確定?？衫靡呀o線網(wǎng)絡(luò)的所有可能信道和該網(wǎng)絡(luò)已有節(jié)點(diǎn)路由特性數(shù)據(jù)，近似推算出Li間的定量方位關(guān)系。

5.3 樹型層次結(jié)構(gòu)路由協(xié)議

路由層協(xié)議如下:下行時(shí)，發(fā)送節(jié)點(diǎn)根據(jù)目標(biāo)節(jié)點(diǎn)地址，在發(fā)送節(jié)點(diǎn)的Sij［p］中搜索該目標(biāo)節(jié)點(diǎn)地址，確定或選擇發(fā)送節(jié)點(diǎn)至下一層的信道。發(fā)送節(jié)點(diǎn)至下一層的信道存放在發(fā)送節(jié)點(diǎn)下行路由Fi［n］中，可均衡選擇，以達(dá)到對電池能量的均衡消耗。逐層下行數(shù)據(jù)，逐層均衡選擇可用信道，直至數(shù)據(jù)傳到目標(biāo)節(jié)點(diǎn)。上行時(shí)，由于本網(wǎng)絡(luò)的上行目標(biāo)節(jié)點(diǎn)就是0層節(jié)點(diǎn)，因此發(fā)送節(jié)點(diǎn)在其上行路由Ei［m］中確定或選擇發(fā)送至上一層的信道，并逐層上行數(shù)據(jù)，逐層均衡選擇可用信道，直至數(shù)據(jù)傳到目標(biāo)節(jié)點(diǎn)。在數(shù)據(jù)上下行的過程中，若發(fā)送節(jié)點(diǎn)的Ei［m］或Fi［k］路由失效，可在其Hi［k］中確定或選擇信道，以傳送上下行數(shù)據(jù)。

5.4 數(shù)據(jù)傳輸丟包處理

在無線數(shù)據(jù)傳輸過程中，丟包現(xiàn)象經(jīng)常發(fā)生，環(huán)境參數(shù)的變化、電源參數(shù)的波動(dòng)、信號參數(shù)受到干擾等都會(huì)導(dǎo)致丟包現(xiàn)象。但丟包問題必須解決，否則就相當(dāng)于路由不通。本文利用nRF24L01硬件的自動(dòng)應(yīng)答與重發(fā)功能，設(shè)定5次點(diǎn)到點(diǎn)之間的自動(dòng)應(yīng)答與重發(fā)。若5次應(yīng)答與重發(fā)都不成功，則發(fā)送節(jié)點(diǎn)選擇其他可能路徑，并根據(jù)該節(jié)點(diǎn)失效的次數(shù)決定選擇上傳該節(jié)點(diǎn)失效的信息。

6 樹型層次結(jié)構(gòu)路由算法

路由算法是具體實(shí)現(xiàn)路由協(xié)議的一種思路與方法，是數(shù)據(jù)傳輸程序設(shè)計(jì)的一種邏輯結(jié)構(gòu)［10］，決定了目標(biāo)程序的正確性、可靠性、容錯(cuò)性、通用性和靈活性。

6.1 基本路由算法

路由算法作用于節(jié)點(diǎn)進(jìn)行數(shù)據(jù)上下行傳輸?shù)目刂瞥绦蛑?，是?shù)據(jù)傳輸程序的一部分?；韭酚伤惴ㄈ缦隆?/p>

① 發(fā)送節(jié)點(diǎn)在Fi［n］或Ei［m］中計(jì)算可用信道，選定一信道，發(fā)送數(shù)據(jù)包。

②若所選信道成功接收，則轉(zhuǎn)步驟⑤，否則轉(zhuǎn)步驟③。

③ 在Fi［n］或Ei［m］及Hi［k］中計(jì)算信道，如有可選信道，則發(fā)送數(shù)據(jù)包，轉(zhuǎn)步驟②;如無信道可選，轉(zhuǎn)步驟④。

④如是發(fā)送節(jié)點(diǎn)主動(dòng)發(fā)送數(shù)據(jù)，則失敗;否則向該節(jié)點(diǎn)的發(fā)送方發(fā)送數(shù)據(jù)傳輸失敗信息。

⑤節(jié)點(diǎn)配置為接收狀態(tài)，等待處理節(jié)點(diǎn)事務(wù)。

6.2 數(shù)據(jù)傳輸失敗路由算法

數(shù)據(jù)傳輸失敗路由算法具體如下。

①收到數(shù)據(jù)傳輸失敗信息。

②判斷是上行失敗還是下行失敗，若是下行失敗，則選擇Fi［n］計(jì)算另一個(gè)可用信道;若是上行失敗，則選擇Ei［m］和Hi［k］計(jì)算另一個(gè)可用信道。

③如存在另一個(gè)可用信道，則發(fā)送數(shù)據(jù)，并轉(zhuǎn)步驟⑥;如不存在，則轉(zhuǎn)步驟④。

④判斷本節(jié)點(diǎn)是否為原發(fā)送節(jié)點(diǎn)，若是，則發(fā)送失敗，轉(zhuǎn)步驟⑥，否則轉(zhuǎn)步驟⑤。

⑤查找到最近一次轉(zhuǎn)發(fā)數(shù)據(jù)所用的信道，發(fā)送數(shù)據(jù)傳輸失敗信息。

⑥節(jié)點(diǎn)配置為接收狀態(tài)，等待處理節(jié)點(diǎn)事務(wù)。

6.3 新節(jié)點(diǎn)入網(wǎng)算法

在本系統(tǒng)中，新節(jié)點(diǎn)入網(wǎng)要解決的問題是新節(jié)點(diǎn)在該網(wǎng)絡(luò)中的網(wǎng)絡(luò)位置是中間節(jié)點(diǎn)還是終節(jié)點(diǎn)，網(wǎng)絡(luò)層次號是什么。新節(jié)點(diǎn)入網(wǎng)算法具體如下。

①廣播入網(wǎng)信息，要求響應(yīng)節(jié)點(diǎn)的0通道地址IDi。

② 如有不同0通道地址IDi，則記入Ei［m］中，并上傳新節(jié)點(diǎn)的0通道地址IDi，轉(zhuǎn)步驟①，否則轉(zhuǎn)步驟③。

③ 分析Ei［m］，如有層次號差大于2的，本節(jié)點(diǎn)層次號取其中間的一個(gè)數(shù);否則任取已知層次號中的一個(gè)，轉(zhuǎn)步驟④;如無數(shù)據(jù)，則入網(wǎng)失敗。

④上傳新節(jié)點(diǎn)路由特性數(shù)據(jù)。

⑤配置無線模塊為接收狀態(tài)，等待處理節(jié)點(diǎn)事務(wù)。

7 結(jié)束語

本文采用31個(gè)節(jié)點(diǎn)組成了一個(gè)無線傳感器網(wǎng)絡(luò)測溫系統(tǒng)并進(jìn)行了測試，其中1個(gè)節(jié)點(diǎn)作為0層節(jié)點(diǎn)，負(fù)責(zé)與上位計(jì)算機(jī)通信，其他30個(gè)節(jié)點(diǎn)構(gòu)成5層樹型層次結(jié)構(gòu)網(wǎng)絡(luò)。該網(wǎng)絡(luò)能成功組網(wǎng)，數(shù)據(jù)上下行正常。網(wǎng)絡(luò)的工作方式主要為網(wǎng)絡(luò)節(jié)點(diǎn)主動(dòng)上傳數(shù)據(jù)。由0層節(jié)點(diǎn)每隔一定時(shí)間(如90 min)向全網(wǎng)發(fā)送一次校時(shí)信號，使全網(wǎng)節(jié)點(diǎn)時(shí)間同步。每個(gè)節(jié)點(diǎn)隔5 min上傳一次數(shù)據(jù)，各節(jié)點(diǎn)第一次上傳數(shù)據(jù)的時(shí)刻可由該節(jié)點(diǎn)0通道地址數(shù)據(jù)(0～65 535)加3得到，單位為秒(3為各節(jié)點(diǎn)之間的發(fā)送間隔即3 s)。本文提出的時(shí)間驅(qū)動(dòng)工作方式不會(huì)出現(xiàn)無線信道擁擠的現(xiàn)象，節(jié)省了處理信道擁擠的開銷和信息傳輸時(shí)間。該樹型層次結(jié)構(gòu)網(wǎng)絡(luò)通信速度快，可均衡使用信道，路由明晰，有較好的網(wǎng)絡(luò)連通性;路由算法具有一定的鍵壯性，較好地保證了該網(wǎng)絡(luò)的可靠性與可用性，易于工程實(shí)現(xiàn)。

［1］張學(xué).無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂疲跩］.軟件學(xué)報(bào)，2007，18(4):945.

［2］李建中，高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，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］ 任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2004，14(7):1283.

［5］王樹禾.數(shù)學(xué)模型基礎(chǔ)［M］.合肥:中國科學(xué)技術(shù)大學(xué)出版社，1996:178.

［6］王朝瑞.圖論［M］.北京:北京理工大學(xué)出版社，1987:236.

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

［8］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:156.

［9］繆強(qiáng)，鄭扣根.無線傳感器網(wǎng)絡(luò)的路由協(xié)議設(shè)計(jì)研究［J］.計(jì)算機(jī)應(yīng)用研究，2004(3):35.

［10］Bars S.計(jì)算機(jī)算法設(shè)計(jì)和分析引論［M］.上海:復(fù)旦大學(xué)出版社，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。

作者于標(biāo)(1962-)，男，1983年畢業(yè)于山東科技大學(xué)電氣自動(dòng)化專業(yè)，獲碩士學(xué)位，副教授;主要從事無線傳感器網(wǎng)絡(luò)技術(shù)、微機(jī)測控技術(shù)、自動(dòng)控制理論與應(yīng)用的研究。