基于無線傳感器網(wǎng)絡(luò)的拓撲控制算法

蔣國帥 程 璞

（安徽理工大學(xué)電氣與信息工程學(xué)院，安徽 淮南232001）

基于無線傳感器網(wǎng)絡(luò)的拓撲控制算法

蔣國帥 程 璞

（安徽理工大學(xué)電氣與信息工程學(xué)院，安徽 淮南232001）

拓撲控制在無線傳感器網(wǎng)絡(luò)中具有舉足輕重的作用，對于延長生命周期、減小通信干擾、提高通信效率方面具有重要作用。在提出了無線傳感器網(wǎng)絡(luò)拓撲控制的設(shè)計目標后，從功率控制和分簇拓撲控制兩個方向去舉例解釋當前兩個主流算法的現(xiàn)象。

無線傳感器網(wǎng)絡(luò)；拓撲控制；功率控制；分簇拓撲控制

0 引言

隨著德國工業(yè)4.0的推進，無線傳感器網(wǎng)絡(luò)也得到了很大的發(fā)展，而無線傳感器網(wǎng)路在社會各個領(lǐng)域有著無可替代的作用。無線傳感器網(wǎng)絡(luò)是由在監(jiān)測區(qū)域內(nèi)部署大量的網(wǎng)絡(luò)節(jié)點并且通過無線通行方式通信的網(wǎng)絡(luò)。但是在無線傳感器網(wǎng)絡(luò)中，節(jié)點通常使用電池供電，而一般無線傳感器網(wǎng)路都是比較龐大的，并且由于其環(huán)境條件使其更換電池相當?shù)牟环奖?，所以，想要充分利用?jié)點有限的能量去完成數(shù)據(jù)的融合和轉(zhuǎn)發(fā)，就必須有一個好的拓撲控制機制來優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，這樣可以合理利用能量來達到延長網(wǎng)絡(luò)的生命周期。

1 無線傳感器網(wǎng)絡(luò)拓撲控制的設(shè)計目標

對于無線傳感器網(wǎng)絡(luò)來說，一個良好的網(wǎng)絡(luò)拓撲結(jié)構(gòu)能夠有效的提高路由協(xié)議和MAC協(xié)議的效率；在保證網(wǎng)絡(luò)節(jié)點的連通性、降低能量的損耗、延長網(wǎng)絡(luò)生命周期、減小節(jié)點間的通信干擾、提高通信效率等方面具有很好的作用，所以，在以下幾個方面作為無線傳感器網(wǎng)絡(luò)拓撲結(jié)構(gòu)的設(shè)計目標。

1.1 保證監(jiān)測區(qū)域覆蓋和網(wǎng)絡(luò)連通

由于覆蓋控制是拓撲控制的基本問題，故網(wǎng)絡(luò)覆蓋質(zhì)量成為首要考慮的目標。即在保證一定覆蓋質(zhì)量的前提下，也要保證網(wǎng)絡(luò)的連通性，這樣才能既能有效的監(jiān)測目標區(qū)域內(nèi)的問題和現(xiàn)象，又能保證及時的將監(jiān)測結(jié)果傳遞給其它網(wǎng)絡(luò)節(jié)點，讓其做出處理。

1.2 合理利用能量，延長網(wǎng)絡(luò)生命周期

由于傳感器網(wǎng)路中的節(jié)點能量是由電池提供的，能量有限，所以合理利用能量也是保證網(wǎng)路生命周期不可忽視的問題之一。拓撲控制的一個重要目標就是在保證網(wǎng)絡(luò)連通性和覆蓋質(zhì)量的情況下，盡量合理高效地使用網(wǎng)絡(luò)能量，延長整個網(wǎng)絡(luò)的生存時間。

1.3 減小節(jié)點間的通信干擾，提高網(wǎng)絡(luò)通信效率

一般情況下無線傳感器網(wǎng)絡(luò)中節(jié)點數(shù)目比較多且布置密集，如果每個節(jié)點都由其自身最大的功率進行通信時，會加劇節(jié)點間的通信干擾，減低通信效率，同時也會造成能量的浪費；同時如果選擇太小的發(fā)射功率，無法保證網(wǎng)絡(luò)的連通性質(zhì)量。所以要在連通性和通信干擾間尋找一個平衡點。

1.4 確定移動節(jié)點和骨干節(jié)點，便于數(shù)據(jù)的傳輸與處理

在無線傳感器網(wǎng)絡(luò)中，數(shù)據(jù)的轉(zhuǎn)發(fā)需要通過移動的節(jié)點，而移動節(jié)點的確定則是由拓撲控制來選擇確定的。而傳感器網(wǎng)絡(luò)中的數(shù)據(jù)還需要進行融合，數(shù)據(jù)的融合則需要通過骨干節(jié)點發(fā)給專門收集數(shù)據(jù)的節(jié)點。所以，對無線傳感器網(wǎng)絡(luò)拓撲結(jié)構(gòu)的優(yōu)化，是對路由協(xié)議、數(shù)據(jù)融合和數(shù)據(jù)傳輸提供很好的基礎(chǔ)。

2 無線傳感器網(wǎng)路拓撲控制的算法

無線傳感器網(wǎng)絡(luò)的拓撲控制主要研究的方向是在保證一定的網(wǎng)絡(luò)連通性和覆蓋質(zhì)量的前提下，通過功率控制和簇頭節(jié)點的選擇，適當?shù)厝コ恍┎槐匾耐ㄐ沛溌罚纬梢粋€數(shù)據(jù)處理和轉(zhuǎn)發(fā)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化。即無線傳感器網(wǎng)路的拓撲控制方式按照研究方向可以分為兩類：功率控制和分簇拓撲控制。功率控制就是通過選擇合適的發(fā)射功率，在保證網(wǎng)絡(luò)連通性和覆蓋質(zhì)量的前提下，將其能量損耗降到最低。分簇拓撲控制就是利用合理的分簇算法，選擇出一些節(jié)點成為簇頭節(jié)點形成一個處理和轉(zhuǎn)發(fā)數(shù)據(jù)的骨干網(wǎng)絡(luò)，其他非簇頭節(jié)點可以通過休眠機制來選擇關(guān)閉節(jié)點，來達到節(jié)能的目的。

2.1 功率控制算法

無線傳感器網(wǎng)絡(luò)中節(jié)點的功率控制是通過對節(jié)點發(fā)射功率的動態(tài)調(diào)整和合理設(shè)置，在保證網(wǎng)絡(luò)連通性、覆蓋質(zhì)量的同時，通過一些方法使得整個網(wǎng)路中節(jié)點的能量消耗最小，從而延長網(wǎng)絡(luò)的生命周期。目前，功率控制算法主要有基于鄰近圖的DRNG算法和DLMST算法，基于方向控制的CBTC算法，基于節(jié)點度的LMA算法和LMN算法，與路由協(xié)議結(jié)合的COMPOW算法等等。

以COMPOW算法為例，其基本的原則就是所有的傳感器節(jié)點使用相同的發(fā)射功率，在保證一定的網(wǎng)絡(luò)連通性的前提下，使其功率最小。功率的最小化是為了在降低傳輸過程中能耗的同時提高網(wǎng)絡(luò)的吞吐量，因此，COMPOW在延長網(wǎng)絡(luò)生命周期、降低MAC層沖突中占據(jù)優(yōu)勢。COMPOW在不同功率層上建立路由表，在每個路由表中同時反映出節(jié)點連通性的數(shù)據(jù)，最終選擇在全局連通性相同的條件下選擇最低功率。當然，功率的一致性也導(dǎo)致了在節(jié)點分布不均勻是會導(dǎo)致所有節(jié)點選擇過大的發(fā)射功率，這是違背設(shè)計原則的，同時功率的最小化也使得拓撲結(jié)構(gòu)不具備較好的容錯能力。

2.2 分簇拓撲控制算法

分簇拓撲控制算法主要原則就是由簇頭節(jié)點組成骨干網(wǎng)絡(luò)，讓骨干網(wǎng)絡(luò)的通信模式始終處于開啟狀態(tài)，而其它的普通節(jié)點則進入睡眠狀態(tài)（當然也不一定），這樣就可以有效的降低網(wǎng)絡(luò)中能量的損耗，延長網(wǎng)絡(luò)的生命周期。

具體的過程是先將全局網(wǎng)絡(luò)拓撲劃分為相連的簇區(qū)域，在每個簇區(qū)域內(nèi)用合理的分簇算法選擇簇頭，由各個區(qū)域的簇頭組成骨干網(wǎng)絡(luò)，其他的節(jié)點則是普通節(jié)點網(wǎng)絡(luò)，在通常情況下，骨干網(wǎng)絡(luò)正常運行，負責(zé)執(zhí)行網(wǎng)路的數(shù)據(jù)融合和轉(zhuǎn)發(fā)的任務(wù)，而普通節(jié)點網(wǎng)絡(luò)則處于休眠狀態(tài)。當然簇頭也不是一成不變的，當通信的鏈路有更好的選擇時，分簇算法會重新選擇簇頭，這樣可以始終讓整個網(wǎng)絡(luò)的能耗最低。分簇拓撲控制算法主要有 GAF算法、LEACH算法，TopDisc算法、CLUSTERPOW算法等。

以GAF算法為例，該算法是由Xu等人提出一種基于地理位置的拓撲算法，它將監(jiān)測區(qū)域劃分成非常小的簇區(qū)域，并在每個區(qū)域中利用分簇算法選擇產(chǎn)生一個簇頭節(jié)點，此時只有簇頭節(jié)點保持活躍狀態(tài)，保證骨干網(wǎng)絡(luò)正常運行，而其它普通節(jié)點則處于睡眠狀態(tài)。GAF算法具體有兩個執(zhí)行階段。第一個階段就是簇區(qū)域的劃分，為了保證相鄰區(qū)域中節(jié)點能夠正常通信，就必須保證節(jié)點發(fā)射半徑R和區(qū)域邊長r滿足一定的關(guān)系即。第二個階段就是簇區(qū)域中簇頭的選擇，每個節(jié)點都處于活躍、被發(fā)現(xiàn)和睡眠三個狀態(tài)。在網(wǎng)絡(luò)初始階段，所以節(jié)點都處于被發(fā)現(xiàn)階段，通過分簇算法選擇出簇頭，同時發(fā)出信息抑制同一區(qū)域內(nèi)其它節(jié)點成為簇頭，而其它節(jié)點則自動處于睡眠狀態(tài)，當經(jīng)過一定的周期時間時，會再次選擇簇頭選擇，以達到鏈路最優(yōu)。但是這種偵聽占用不少能量也是無法避免的。

2.3 分簇拓撲結(jié)構(gòu)和功率控制相結(jié)合的算法

分簇拓撲控制和功率控制是網(wǎng)絡(luò)拓撲控制兩個主流研究方向，當然也有將這兩種方式結(jié)合起來的算法，比較成功的是Ad hoc網(wǎng)絡(luò)設(shè)計算法（ANDA）。該算法可以用簇頭通過功率控制來控制簇的大小，因為在此網(wǎng)絡(luò)中可以看成其生命周期主要是由簇頭的生命周期來決定，畢竟簇頭要完成該網(wǎng)絡(luò)的大部分工作，故能量消耗應(yīng)該在簇頭之間尋找平衡。

Ad hoc網(wǎng)絡(luò)設(shè)計算法的假設(shè)條件是普通節(jié)點和簇頭的位置是已經(jīng)確定的，并且通信量在節(jié)點之間是均勻分布的，而簇頭的生命周期是與其初始能量供應(yīng)成正比，與br?+cm成反比，其中b、c是常數(shù)，r是簇頭覆蓋區(qū)域的半徑，?是路徑損耗系數(shù)，m是簇內(nèi)節(jié)點數(shù)目。為了延長網(wǎng)絡(luò)生命周期其實就是為了使簇頭中的最小生命周期最長。該算法對于靜態(tài)網(wǎng)絡(luò)來說可以通過貪婪算法來求得最優(yōu)解，將節(jié)點分配給最長生命周期的簇頭，對于所有節(jié)點都有此操作，而對于動態(tài)網(wǎng)絡(luò)來說需要一個額重新的分配過程，雖然無法求得最優(yōu)解，但是其實際性能還是相當不錯的。

3 結(jié)束語網(wǎng)絡(luò)拓撲結(jié)構(gòu)對于無線傳感器的發(fā)展有著不可忽視的作用，雖然大部分的研究還只限于理論研究，運用到實際中的還比較少，這與其技術(shù)發(fā)展的不成熟息息相關(guān)。比如說目前研究的網(wǎng)絡(luò)拓撲結(jié)構(gòu)都是在理想狀況下，而現(xiàn)實中有諸多影響因素都沒有考慮進去，導(dǎo)致其實用性很差，另外網(wǎng)絡(luò)拓撲結(jié)構(gòu)的容錯性、可靠性、擴展性、網(wǎng)絡(luò)延遲等性能研究的還不夠深入。但是相信隨著網(wǎng)絡(luò)拓撲結(jié)構(gòu)研究的深入，其技術(shù)日益成熟，無線傳感器網(wǎng)絡(luò)必將迎來嶄新的未來。

［1］邱天爽，唐洪，等.無線傳感器網(wǎng)絡(luò)協(xié)議與體系結(jié)構(gòu)[M].北京：電子工業(yè)出版社，2007．

［2］劉林峰，金杉.無線傳感器網(wǎng)絡(luò)的拓撲控制算法綜述[J].計算機科學(xué)，2008．

［3］徐平平.無線傳感器網(wǎng)絡(luò)[M].北京：電子工業(yè)出版社，2013．

［4］張燕．無線傳感器網(wǎng)路、原理、設(shè)計和應(yīng)用[M].北京：機械工業(yè)出版社，2015．

［責(zé)任編輯：田吉捷］