蔣國帥 程 璞
(安徽理工大學電氣與信息工程學院,安徽 淮南232001)
基于無線傳感器網絡的拓撲控制算法
蔣國帥 程 璞
(安徽理工大學電氣與信息工程學院,安徽 淮南232001)
拓撲控制在無線傳感器網絡中具有舉足輕重的作用,對于延長生命周期、減小通信干擾、提高通信效率方面具有重要作用。在提出了無線傳感器網絡拓撲控制的設計目標后,從功率控制和分簇拓撲控制兩個方向去舉例解釋當前兩個主流算法的現象。
無線傳感器網絡;拓撲控制;功率控制;分簇拓撲控制
隨著德國工業4.0的推進,無線傳感器網絡也得到了很大的發展,而無線傳感器網路在社會各個領域有著無可替代的作用。無線傳感器網絡是由在監測區域內部署大量的網絡節點并且通過無線通行方式通信的網絡。但是在無線傳感器網絡中,節點通常使用電池供電,而一般無線傳感器網路都是比較龐大的,并且由于其環境條件使其更換電池相當的不方便,所以,想要充分利用節點有限的能量去完成數據的融合和轉發,就必須有一個好的拓撲控制機制來優化網絡的拓撲結構,這樣可以合理利用能量來達到延長網絡的生命周期。
對于無線傳感器網絡來說,一個良好的網絡拓撲結構能夠有效的提高路由協議和MAC協議的效率;在保證網絡節點的連通性、降低能量的損耗、延長網絡生命周期、減小節點間的通信干擾、提高通信效率等方面具有很好的作用,所以,在以下幾個方面作為無線傳感器網絡拓撲結構的設計目標。
1.1 保證監測區域覆蓋和網絡連通
由于覆蓋控制是拓撲控制的基本問題,故網絡覆蓋質量成為首要考慮的目標。即在保證一定覆蓋質量的前提下,也要保證網絡的連通性,這樣才能既能有效的監測目標區域內的問題和現象,又能保證及時的將監測結果傳遞給其它網絡節點,讓其做出處理。
1.2 合理利用能量,延長網絡生命周期
由于傳感器網路中的節點能量是由電池提供的,能量有限,所以合理利用能量也是保證網路生命周期不可忽視的問題之一。拓撲控制的一個重要目標就是在保證網絡連通性和覆蓋質量的情況下,盡量合理高效地使用網絡能量,延長整個網絡的生存時間。
1.3 減小節點間的通信干擾,提高網絡通信效率
一般情況下無線傳感器網絡中節點數目比較多且布置密集,如果每個節點都由其自身最大的功率進行通信時,會加劇節點間的通信干擾,減低通信效率,同時也會造成能量的浪費;同時如果選擇太小的發射功率,無法保證網絡的連通性質量。所以要在連通性和通信干擾間尋找一個平衡點。
1.4 確定移動節點和骨干節點,便于數據的傳輸與處理
在無線傳感器網絡中,數據的轉發需要通過移動的節點,而移動節點的確定則是由拓撲控制來選擇確定的。而傳感器網絡中的數據還需要進行融合,數據的融合則需要通過骨干節點發給專門收集數據的節點。所以,對無線傳感器網絡拓撲結構的優化,是對路由協議、數據融合和數據傳輸提供很好的基礎。
無線傳感器網絡的拓撲控制主要研究的方向是在保證一定的網絡連通性和覆蓋質量的前提下,通過功率控制和簇頭節點的選擇,適當地去除一些不必要的通信鏈路,形成一個數據處理和轉發的網絡結構優化。即無線傳感器網路的拓撲控制方式按照研究方向可以分為兩類:功率控制和分簇拓撲控制。功率控制就是通過選擇合適的發射功率,在保證網絡連通性和覆蓋質量的前提下,將其能量損耗降到最低。分簇拓撲控制就是利用合理的分簇算法,選擇出一些節點成為簇頭節點形成一個處理和轉發數據的骨干網絡,其他非簇頭節點可以通過休眠機制來選擇關閉節點,來達到節能的目的。
2.1 功率控制算法
無線傳感器網絡中節點的功率控制是通過對節點發射功率的動態調整和合理設置,在保證網絡連通性、覆蓋質量的同時,通過一些方法使得整個網路中節點的能量消耗最小,從而延長網絡的生命周期。目前,功率控制算法主要有基于鄰近圖的DRNG算法和DLMST算法,基于方向控制的CBTC算法,基于節點度的LMA算法和LMN算法,與路由協議結合的COMPOW算法等等。
以COMPOW算法為例,其基本的原則就是所有的傳感器節點使用相同的發射功率,在保證一定的網絡連通性的前提下,使其功率最小。功率的最小化是為了在降低傳輸過程中能耗的同時提高網絡的吞吐量,因此,COMPOW在延長網絡生命周期、降低MAC層沖突中占據優勢。COMPOW在不同功率層上建立路由表,在每個路由表中同時反映出節點連通性的數據,最終選擇在全局連通性相同的條件下選擇最低功率。當然,功率的一致性也導致了在節點分布不均勻是會導致所有節點選擇過大的發射功率,這是違背設計原則的,同時功率的最小化也使得拓撲結構不具備較好的容錯能力。
2.2 分簇拓撲控制算法
分簇拓撲控制算法主要原則就是由簇頭節點組成骨干網絡,讓骨干網絡的通信模式始終處于開啟狀態,而其它的普通節點則進入睡眠狀態(當然也不一定),這樣就可以有效的降低網絡中能量的損耗,延長網絡的生命周期。
具體的過程是先將全局網絡拓撲劃分為相連的簇區域,在每個簇區域內用合理的分簇算法選擇簇頭,由各個區域的簇頭組成骨干網絡,其他的節點則是普通節點網絡,在通常情況下,骨干網絡正常運行,負責執行網路的數據融合和轉發的任務,而普通節點網絡則處于休眠狀態。當然簇頭也不是一成不變的,當通信的鏈路有更好的選擇時,分簇算法會重新選擇簇頭,這樣可以始終讓整個網絡的能耗最低。分簇拓撲控制算法主要有 GAF算法、LEACH算法,TopDisc算法、CLUSTERPOW算法等。
以GAF算法為例,該算法是由Xu等人提出一種基于地理位置的拓撲算法,它將監測區域劃分成非常小的簇區域,并在每個區域中利用分簇算法選擇產生一個簇頭節點,此時只有簇頭節點保持活躍狀態,保證骨干網絡正常運行,而其它普通節點則處于睡眠狀態。GAF算法具體有兩個執行階段。第一個階段就是簇區域的劃分,為了保證相鄰區域中節點能夠正常通信,就必須保證節點發射半徑R和區域邊長r滿足一定的關系即。第二個階段就是簇區域中簇頭的選擇,每個節點都處于活躍、被發現和睡眠三個狀態。在網絡初始階段,所以節點都處于被發現階段,通過分簇算法選擇出簇頭,同時發出信息抑制同一區域內其它節點成為簇頭,而其它節點則自動處于睡眠狀態,當經過一定的周期時間時,會再次選擇簇頭選擇,以達到鏈路最優。但是這種偵聽占用不少能量也是無法避免的。
2.3 分簇拓撲結構和功率控制相結合的算法
分簇拓撲控制和功率控制是網絡拓撲控制兩個主流研究方向,當然也有將這兩種方式結合起來的算法,比較成功的是Ad hoc網絡設計算法(ANDA)。該算法可以用簇頭通過功率控制來控制簇的大小,因為在此網絡中可以看成其生命周期主要是由簇頭的生命周期來決定,畢竟簇頭要完成該網絡的大部分工作,故能量消耗應該在簇頭之間尋找平衡。
Ad hoc網絡設計算法的假設條件是普通節點和簇頭的位置是已經確定的,并且通信量在節點之間是均勻分布的,而簇頭的生命周期是與其初始能量供應成正比,與br?+cm成反比,其中b、c是常數,r是簇頭覆蓋區域的半徑,?是路徑損耗系數,m是簇內節點數目。為了延長網絡生命周期其實就是為了使簇頭中的最小生命周期最長。該算法對于靜態網絡來說可以通過貪婪算法來求得最優解,將節點分配給最長生命周期的簇頭,對于所有節點都有此操作,而對于動態網絡來說需要一個額重新的分配過程,雖然無法求得最優解,但是其實際性能還是相當不錯的。
[1]邱天爽,唐洪,等.無線傳感器網絡協議與體系結構[M].北京:電子工業出版社,2007.
[2]劉林峰,金杉.無線傳感器網絡的拓撲控制算法綜述[J].計算機科學,2008.
[3]徐平平.無線傳感器網絡[M].北京:電子工業出版社,2013.
[4]張燕.無線傳感器網路、原理、設計和應用[M].北京:機械工業出版社,2015.
[責任編輯:田吉捷]