基于有向樹算法的無線傳感器網絡應用研究

繆德俊 于標

摘 要：層次型網絡具有覆蓋度高、擴展性好和可靠性高的優點，受到廣泛重視。但其匯聚節點附近的簇首生命周期短，成為制約它應用的瓶頸。已有研究表明，有多種簇首選擇與路由生成方法，存在一定隨機性和試探性。一個好的網路拓撲是改善此類問題的基礎，提出一種有向樹分簇算法。匯聚節點與檢測節點是同構的，節點通信半徑在幾十米范圍內，構建一種層次型網絡。上層網絡拓撲為退化的有向樹結構，降低上層網絡的復雜度。下層網絡拓撲是一種交叉形星型結構。設置簇首傳輸數據次數，在簇內依次輪換成員節點為新簇首，均衡了簇首能量消耗。網絡拓撲在節點無線信號有效半徑內偵測構建，最大可能地覆蓋了節點分布區域。節點路由特征數據明確，計算量小，易于工程實現，有一定應用價值。

關鍵詞：分簇算法;有向樹;交叉形星型;拓撲;路由;簇首

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.

（編輯 王雪芬）