繆德俊 于標(biāo)

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

關(guān)鍵詞：分簇算法;有向樹;交叉形星型;拓?fù)?路由;簇首

0? ? 引言

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

1? ? 有向樹分簇網(wǎng)絡(luò)拓?fù)?/p>

設(shè)Y個(gè)無線傳感器節(jié)點(diǎn)組成一個(gè)頂點(diǎn)集合，定義頂點(diǎn)集R={r0， r1，…，rx}，U={u00， u10，…，uij}與V={v00，v01，…，vkl}分別是R的兩個(gè)子集。定義圖D=（R，E），E（D）={e0，e1，…，ep}是有序集R×R的一個(gè)子集。定義uij為第i層（i=1，2…，m），第j個(gè)（j=0，1，2…，n）簇首節(jié)點(diǎn)，m和n為不確定自然數(shù)。定義vkl表示第k層（k=1，2…，f），第j個(gè)（j=0，1，2…，g）成員節(jié)點(diǎn)，f和g為不確定自然數(shù)。退化有向樹分簇網(wǎng)絡(luò)拓?fù)淙鐖D1所示。

1.1? 上層網(wǎng)絡(luò)拓?fù)?/p>

簇首節(jié)點(diǎn)能量較易耗盡，本文提出構(gòu)建多條有向通路的設(shè)想，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上延長簇首節(jié)點(diǎn)的生命周期。定義退化有向樹T=（R，U） ，如圖1中粗線所示。退化有向樹T最末層是出度為0的葉子，是一棵只有樹干的退化有向樹。退化有向樹T降低了上層網(wǎng)絡(luò)復(fù)雜性，簡化了路由算法，提高了信息傳輸?shù)乃俣?。相鄰的兩個(gè)簇首節(jié)點(diǎn)，使其只有一條弧bxj關(guān)聯(lián)。對圖T中的頂點(diǎn)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）為頂點(diǎn)uxj與uyj之間的幾何距離，（dx，dy）為uxj與uyj頂點(diǎn)的通信半徑。圖T中的任一條有向鏈u00u1ju2j…uij，由無線信號偵測自然選擇，形成一條有向通路[4]。任一成員節(jié)點(diǎn)vkl都能經(jīng)簇首節(jié)點(diǎn)uij到達(dá)匯聚節(jié)點(diǎn)。

1.2? 下層網(wǎng)絡(luò)拓?fù)?/p>

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

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

圖D=（R，E）是無線信號有效半徑覆蓋范圍內(nèi)一級一級依次建成的，頂點(diǎn)集R={r0， r1，…，rx}中，任一個(gè)頂點(diǎn)ri都可以通過相鄰頂點(diǎn)連通到其他頂點(diǎn)，所以圖D是連通的。若u10與u11的共有成員v04，u10與u20的共有成員v03及ui0與ui1的共有成員v10等頂點(diǎn)不成為共有頂點(diǎn)，只歸屬于其中的一個(gè)簇首，則圖D成為一棵樹。賦邊集E（D）={e0，e1，…，ep}中所有邊的權(quán)為1，定義圖T=（U，E1），E1（T）={t0，t1，…，tq}是邊集E（D）的子集。頂點(diǎn)集U={u00， u10，…，uij}中任一個(gè)頂點(diǎn)uij都可以通過相鄰頂點(diǎn)連通到其他頂點(diǎn)，所以圖T是連通的，定義T為有向樹。T中連通分枝的長度是無線信號偵測的結(jié)果，當(dāng)偵測不到任何節(jié)點(diǎn)時(shí)組網(wǎng)結(jié)束。有向樹算法能得到最大可能覆蓋度，連通分枝的長度在滿足最大可能覆蓋度條件下最短，即每條連通分枝的權(quán)是最小的，所以T是一棵最優(yōu)樹[4]。作為上層網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，是一棵沒有樹葉的樹，稱為退化有向樹。

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

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

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

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

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

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

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

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

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

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

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

4? ? 有向樹分簇算法

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

5? ? 結(jié)語

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

[參考文獻(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)絡(luò)能耗均衡拓?fù)淠Ｐ脱芯?[J].傳感技術(shù)學(xué)報(bào)，2017（8）：1246-1251.

[4]王朝瑞. 圖論[M].北京： 北京理工大學(xué)出版社，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)絡(luò)非均勻分層路由協(xié)議[J].計(jì)算機(jī)科學(xué)，2018（3）：117-125.

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

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

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

[11]王慧嬌，邱贊，董榮勝，等.一種無線傳感器網(wǎng)絡(luò)能耗均衡的自適應(yīng)拓?fù)洳┺乃惴╗J].控制與決策，2019（1）：72-80.

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

（編輯 王雪芬）