一種樹型層次結構的無線傳感器網絡應用研究

于 標

(揚州市職業大學電氣與汽車工程學院，江蘇 揚州 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年畢業于山東科技大學電氣自動化專業，獲碩士學位，副教授;主要從事無線傳感器網絡技術、微機測控技術、自動控制理論與應用的研究。