繆德俊 于標

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

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

0? ? 引言

無線傳感器網(wǎng)絡的結構一般有層次型結構、平面型結構、混合型結構和網(wǎng)格（Mesh）型結構。層次型網(wǎng)絡結構是一種分級結構，由上層網(wǎng)絡和下層網(wǎng)絡兩層組成。簇首節(jié)點擔負網(wǎng)絡數(shù)據(jù)傳輸任務，距匯聚節(jié)點越近的簇首，其數(shù)據(jù)傳輸量越大，能量消耗也越快。如何節(jié)省簇首節(jié)點的能耗，延長其生命期已有許多研究，取得了一些改進，但此問題并未完全解決。簇首節(jié)點分布的合理性和生命周期是層次型網(wǎng)絡構建的關鍵問題，主要表現(xiàn)在分簇方法及網(wǎng)絡拓撲控制算法上[2]。本文提出一種有向樹分簇算法，根據(jù)無線信號有效半徑偵測簇首節(jié)點和成員節(jié)點，為匯聚節(jié)點建立盡可能多的有向通路。提出在匯聚節(jié)點無線信號偵測范圍內(nèi)布置的節(jié)點，均作為簇首節(jié)點使用，稱為第一級簇首節(jié)點。第一級簇首節(jié)點各自與匯聚節(jié)點建立一條有向通道，作為通道的第一個首節(jié)點，由此獲得多條通信路徑，利用第一級簇首的數(shù)量延長簇首的生命期。第一級簇首節(jié)點偵測到的所有第二級節(jié)點中，通過節(jié)點數(shù)量控制與通信能否覆蓋分配給第一級簇首節(jié)點，成為它們的成員節(jié)點。如此，直至新簇首不能偵測到其他節(jié)點為止。分簇算法控制了層次型網(wǎng)絡拓撲結構和網(wǎng)絡性能[1]。這種多條并行數(shù)據(jù)傳輸路徑，在結構上均衡上層網(wǎng)絡簇首節(jié)點的能耗，延長了簇首生命周期[3]。簇內(nèi)節(jié)點，按照簇首與上層網(wǎng)絡傳輸數(shù)據(jù)的次數(shù)輪換簇首，均衡了簇首能耗。

1? ? 有向樹分簇網(wǎng)絡拓撲

設Y個無線傳感器節(jié)點組成一個頂點集合，定義頂點集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）簇首節(jié)點，m和n為不確定自然數(shù)。定義vkl表示第k層（k=1，2…，f），第j個（j=0，1，2…，g）成員節(jié)點，f和g為不確定自然數(shù)。退化有向樹分簇網(wǎng)絡拓撲如圖1所示。

1.1? 上層網(wǎng)絡拓撲

簇首節(jié)點能量較易耗盡，本文提出構建多條有向通路的設想，從網(wǎng)絡拓撲結構上延長簇首節(jié)點的生命周期。定義退化有向樹T=（R，U） ，如圖1中粗線所示。退化有向樹T最末層是出度為0的葉子，是一棵只有樹干的退化有向樹。退化有向樹T降低了上層網(wǎng)絡復雜性，簡化了路由算法，提高了信息傳輸?shù)乃俣?。相鄰的兩個簇首節(jié)點，使其只有一條弧bxj關聯(lián)。對圖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]。任一成員節(jié)點vkl都能經(jīng)簇首節(jié)點uij到達匯聚節(jié)點。

1.2? 下層網(wǎng)絡拓撲

通常下層網(wǎng)絡是星型結構，一個簇首節(jié)點對應若干個成員節(jié)點。簇首節(jié)點擔負簇內(nèi)成員與上層網(wǎng)絡互傳數(shù)據(jù)的任務，這種結構帶來簇首生命期短的問題[5]。簇內(nèi)節(jié)點都作為備用簇首輪換使用，按簇首與上層網(wǎng)絡傳輸數(shù)據(jù)的次數(shù)依次輪換簇首。提出一種交叉形簇結構，在成員節(jié)點集V={v00， v01，…，vkl}中，若vkl能被兩個簇首節(jié)點的通信半徑覆蓋，則使其成為共有成員。共有成員v03交替使用簇首節(jié)點u10和u20傳輸數(shù)據(jù)，實現(xiàn)相鄰簇間的通信，提供了一定的網(wǎng)絡連通度。

1.3? 有向樹是最優(yōu)樹

圖D=（R，E）是無線信號有效半徑覆蓋范圍內(nèi)一級一級依次建成的，頂點集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中連通分枝的長度是無線信號偵測的結果，當偵測不到任何節(jié)點時組網(wǎng)結束。有向樹算法能得到最大可能覆蓋度，連通分枝的長度在滿足最大可能覆蓋度條件下最短，即每條連通分枝的權是最小的，所以T是一棵最優(yōu)樹[4]。作為上層網(wǎng)絡的拓撲結構，是一棵沒有樹葉的樹，稱為退化有向樹。

1.4? 有向樹網(wǎng)絡構建思路

有向樹網(wǎng)絡拓撲是一種圖，遍歷全圖可以構造有向樹分簇算法網(wǎng)絡。在圖的遍歷過程中，組建上層網(wǎng)絡和下層網(wǎng)絡[5]。兩個簇首節(jié)點uxj和uyj之間（y=x+1），無線信號能否相互覆蓋是弧存在的必要條件。無線傳感器網(wǎng)絡的數(shù)據(jù)傳輸是基本功能，覆蓋度與信息傳遞的快捷性是網(wǎng)絡重要的性能指標[6]。

2? ? 有向樹分簇網(wǎng)絡數(shù)據(jù)鏈路層與物理層

無線傳感器網(wǎng)絡的數(shù)據(jù)傳輸、數(shù)字信號調制等工作是物理層完成的[7]。物理層的功能和性能設計是否合理，決定了節(jié)點電路的功能、可靠性和性能指標[8]。本網(wǎng)絡采用同構節(jié)點電路，遵守了節(jié)點電路低功耗、低成本和小體積的設計目標。

設計性能優(yōu)良的網(wǎng)絡介質訪問控制方法（Medium Access Control，MAC）是數(shù)據(jù)鏈路層的重要任務[9]。節(jié)點身份識別是消除節(jié)點間無線信號沖突的關鍵技術，數(shù)據(jù)幀中包含頻道地址是解決此問題的基礎。圖2數(shù)據(jù)幀格式圖，它由檢測數(shù)據(jù)、頻道地址、網(wǎng)絡命令、簇首節(jié)點層次號等信息組成。數(shù)據(jù)幀的意義影響著數(shù)據(jù)鏈路層的功能，各數(shù)據(jù)項定義如下：網(wǎng)絡命令與狀態(tài)字節(jié)Z0、簇首與成員標志字節(jié)Z1、簇首層次號字節(jié)Z2、簇首起點頻道接收地址（Z3～Z7）、簇首終點接收頻道地址（Z8～Z12）、簇首接收頻道地址（Z13～Z17）、溫度值字節(jié)（Z18～Z19）。定義Z0=（00H～05H）分別為下傳數(shù)據(jù)、上傳數(shù)據(jù)、網(wǎng)絡校時、退網(wǎng)、組網(wǎng)、通路建立等命令。定義Z0=（06H～0BH）分別為上傳成功、組網(wǎng)未結束、組網(wǎng)結束、節(jié)點未入網(wǎng)、節(jié)點入網(wǎng)、共有成員等狀態(tài)。

3? ? 有向樹分簇網(wǎng)絡網(wǎng)絡層

網(wǎng)絡層負責路由選擇或者路由生成，完成數(shù)據(jù)融合等工作[10]。本網(wǎng)絡節(jié)點地址是確定的，節(jié)點間無線信號半徑相互覆蓋。理想情況下，在任一節(jié)點與匯聚節(jié)點之間都能形成一條通信路徑。節(jié)點的無線信號半徑，地理位置及組網(wǎng)算法影響了入網(wǎng)節(jié)點的路由特征數(shù)據(jù)[11]。

3.1? 節(jié)點路由特征數(shù)據(jù)

3.2? 有向樹分簇網(wǎng)絡路由協(xié)議

簇首節(jié)點組成了上層網(wǎng)絡，在匯聚節(jié)點和簇首節(jié)點間可構成若干條有向通路，作為網(wǎng)絡數(shù)據(jù)傳輸?shù)穆窂?。傳感器檢測數(shù)據(jù)上行至u00是網(wǎng)絡的首要任務，u00可將檢測數(shù)據(jù)傳至上位計算機或其他網(wǎng)絡系統(tǒng)[12]。數(shù)據(jù)傳輸方向是兩個，一個是匯聚節(jié)點u00下行網(wǎng)絡命令，另一個是成員節(jié)點上行檢測數(shù)據(jù)。

成員節(jié)點組成了下層網(wǎng)絡，對于簇內(nèi)數(shù)據(jù)傳輸，下行數(shù)據(jù)時，簇首從其Gx[s]中得到成員接收頻道地址，完成發(fā)送頻道地址配置;數(shù)據(jù)上行時，成員節(jié)點從Fx[5]中得到簇首接收頻道地址，完成發(fā)送頻道地址配置，依級傳輸直至數(shù)據(jù)到達匯聚節(jié)點u00。對于簇首輪換，現(xiàn)任簇首達到數(shù)據(jù)傳輸次數(shù)閾值后，從Jx[m]中選擇備用簇首發(fā)送頻道地址，完成發(fā)送頻道地址配置，發(fā)送Dx[5]簇首起點發(fā)送頻道地址與Ex[5]簇首終點發(fā)送頻道地址給備用簇首，實現(xiàn)簇首輪換功能。對于相鄰簇的通信，共有成員達到傳輸數(shù)據(jù)次數(shù)閾值后，從Hx[t]中得到相鄰簇首接收頻道地址，傳送到Fx[5]中，完成共有成員相鄰簇首發(fā)送頻道地址配置。

4? ? 有向樹分簇算法

匯聚節(jié)點u00作為控制節(jié)點發(fā)布組網(wǎng)數(shù)據(jù)幀。組網(wǎng)數(shù)據(jù)幀包括：組網(wǎng)命令（Z0=04H）、u00接收頻道地址P0、簇首層次號Z2∈（1，2，3…，f）等。以第一層簇首組網(wǎng)為例說明一層簇首組網(wǎng)結束情況。若第一層有w條有向通路，那么u00有w個首個簇首節(jié)點。組網(wǎng)結束條件為P0[1]∩P0[2]…∩P0[w]=1，首個簇首節(jié)點組網(wǎng)結束條件從其收到的上傳數(shù)據(jù)幀（Z0=07H）中得到。

5? ? 結語

賦權圖T是一棵最優(yōu)樹，是上層網(wǎng)絡的拓撲。有向樹分簇算法得到的退化有向樹T結構簡單，路由明晰，均衡了簇首能耗。u00依簇首級次順序下傳數(shù)據(jù)，簇首將成員節(jié)點數(shù)據(jù)逐級上傳至u00。匯聚節(jié)點定時發(fā)一次校時信息，網(wǎng)絡可以時間方式驅動工作。有向樹算法簡單，易于工程實現(xiàn)。

[參考文獻]

[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]王景嫻，陳珍萍，趙政坤，等.無線傳感器網(wǎng)絡能耗均衡拓撲模型研究 [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分層分簇路由協(xié)議[J].控制工程，2017（12）：2560-2565.

[7]陶志勇，王和章.基于新型聚類的無線傳感器網(wǎng)絡非均勻分層路由協(xié)議[J].計算機科學，2018（3）：117-125.

[8]黃延輝，伊凱，崔更申，等. 基于非均勻分簇的無線傳感器網(wǎng)絡分層路由協(xié)議[J].計算機應用，2016（1）：66-71.

[9]余修武，劉琴，劉永，等. 深井無線傳感器網(wǎng)絡非均勻分簇路由協(xié)議[J].傳感技術學報，2018（7）：1097-1100.

[10]王繼紅，石文孝.認知無線傳感器網(wǎng)絡分簇路由協(xié)議綜述[J].通信學報，2018（11）：156-169.

[11]王慧嬌，邱贊，董榮勝，等.一種無線傳感器網(wǎng)絡能耗均衡的自適應拓撲博弈算法[J].控制與決策，2019（1）：72-80.

[12]周新蓮，朱澤鵬.無線傳感器骨干網(wǎng)絡路由算法[J].吉林大學學報（理學版），2019（2）：363-368.

（編輯 王雪芬）