無線傳感器網(wǎng)絡(luò)的拓撲控制技術(shù)

1、無線傳感器網(wǎng)絡(luò)的拓撲控制技術(shù)拓撲控制技術(shù)是無線傳感器網(wǎng)絡(luò)中最重要的技術(shù)之一。在由無線傳感器網(wǎng)絡(luò)生成的網(wǎng)絡(luò)拓撲中,可以直接通信的兩個結(jié)點之間存在一條拓撲邊。如果沒有拓撲控制,所有結(jié)點都會以最大無線傳輸功率工作。在這種情況下,一方面,結(jié)點有限的能量將被通信部件快速消耗,降低了網(wǎng)絡(luò)的生命周期。同時,網(wǎng)絡(luò)中每個結(jié)點的無線信號將覆蓋大量其他結(jié)點,造成無線信號沖突頻繁,影響結(jié)點的無線通信質(zhì)量,降低網(wǎng)絡(luò)的吞吐率。另一方面,在生成的網(wǎng)絡(luò)拓撲中將存在大量的邊,從而導(dǎo)致網(wǎng)絡(luò)拓撲信息量大,路由計算復(fù)雜,浪費了寶貴的計算資源。因此,需要研究無線傳感器網(wǎng)絡(luò)中的拓撲控制問題,在維持拓撲的某些全局性質(zhì)的前提下,通過調(diào)整結(jié)點

2、的發(fā)送功率來延長網(wǎng)絡(luò)生命周期,提高網(wǎng)絡(luò)吞吐量,降低網(wǎng)絡(luò)干擾,節(jié)約結(jié)點資源。應(yīng)滿足的性質(zhì)拓撲控制算法的目標是通過控制結(jié)點的傳輸范圍使生成的網(wǎng)絡(luò)拓撲滿足一定的性質(zhì),以延長網(wǎng)絡(luò)生命周期,降低網(wǎng)絡(luò)干擾,提高吞吐率。一般假設(shè)結(jié)點分布在二維平面上,所有結(jié)點都是同構(gòu)的,都使用無向天線。以有向圖建模無線傳感器網(wǎng)絡(luò),如果結(jié)點i的傳輸功率Pi大于從結(jié)點i到結(jié)點j需要的傳輸功率Pij,則結(jié)點i到結(jié)點j之間有一條有向邊。所有結(jié)點都以最大功率工作時所生成的拓撲稱為UDG圖(Unit Disk Graph。拓撲控制應(yīng)使網(wǎng)絡(luò)拓撲滿足下列性質(zhì)中的一個或幾個:連通性為了實現(xiàn)結(jié)點間的互相通信,生成的拓撲必須保證連通性,即從任何一

3、個結(jié)點都可以發(fā)送消息到另外一個結(jié)點。連通性是任何拓撲控制算法都必須保證的一個性質(zhì)。由UDG圖的定義可以知道,UDG圖的連通性是網(wǎng)絡(luò)能夠提供的最大連通性,因此一般假定UDG圖是連通的。所以,任何拓撲控制算法生成的拓撲都是UDG圖的子圖。對稱性指如果從結(jié)點i 到結(jié)點j有一條邊,那么一定存在從結(jié)點j到結(jié)點i的邊。由于非對稱鏈路在目前的MAC協(xié)議中沒有得到很好的支持,而且非對稱鏈路通信的開銷很大,因此一般都要求生成的拓撲中鏈路是對稱的。稀疏性指生成的拓撲中的邊數(shù)為O(n,其中n是結(jié)點個數(shù)。減少拓撲中的邊數(shù)可以有效減少網(wǎng)絡(luò)中的干擾,提高網(wǎng)絡(luò)的吞吐率。稀疏性還可以簡化路由計算。平面性指生成的拓撲中沒有兩條

4、邊相交。由圖論可知,滿足平面性一定滿足稀疏性。地理路由協(xié)議是一種十分適合計算和存儲能力有限的無線傳感器結(jié)點的路由協(xié)議,它不需要維護路由表和進行復(fù)雜的路由計算,只需要按照一定的規(guī)則轉(zhuǎn)發(fā)消息。但當?shù)讓油負洳皇瞧矫鎴D時,地理路由協(xié)議不能保證消息轉(zhuǎn)發(fā)的可達性。因此,當結(jié)點運行地理路由協(xié)議時,要求生成的拓撲必須滿足平面性。結(jié)點度數(shù)有界指在生成的拓撲中結(jié)點的鄰居個數(shù)小于一個常數(shù)d。降低結(jié)點的度數(shù)可以減少結(jié)點轉(zhuǎn)發(fā)消息的數(shù)量和路由計算的復(fù)雜度。Spanner性質(zhì)指在生成的拓撲中任何兩個結(jié)點間的距離小于它們在UDG圖中距離的常數(shù)倍。研究方法目前對拓撲控制的研究可以分為兩大類。一類是計算幾何方法,以某些幾何結(jié)構(gòu)為

5、基礎(chǔ)構(gòu)建網(wǎng)絡(luò)的拓撲,以滿足某些性質(zhì)。另一類是概率分析方法,在結(jié)點按照某種概率密度分布情況下,計算使拓撲以大概率滿足某些性質(zhì)時結(jié)點所需的最小傳輸功率和最小鄰居個數(shù)。1.計算幾何方法該方法常使用的幾何結(jié)構(gòu)有如下幾種:最小生成樹(MST 網(wǎng)絡(luò)拓撲是以結(jié)點間的歐式距離為度量的最小生成樹。結(jié)點的傳輸半徑設(shè)為與該結(jié)點相鄰的最長邊的長度。以MST為拓撲的網(wǎng)絡(luò)能保證網(wǎng)絡(luò)的連通性。由于在分布式環(huán)境下構(gòu)造MST開銷巨大,一種折中的方法是結(jié)點采用局部MST方法設(shè)置傳輸范圍。GG圖(Gabriel Graph 在傳輸功率正比傳輸距離的平方時,GG圖是最節(jié)能的拓撲。MST是GG 圖的子圖,GG圖也滿足連通性。 RNG圖

6、(Relative Neighbor Graph 其稀疏程度在MST 和GG圖之間,連通性也在MST和GG圖之間,優(yōu)于MST,沖突干擾優(yōu)于GG圖,是兩者的折中。RNG圖易于用分布式算法構(gòu)造。DT圖(Delaunay Triangulation UDG與DT圖的交集稱為UDel圖(Unit Delaunay Triangulation。UDel圖是稀疏的平面圖,適合于地理路由協(xié)議、節(jié)能、簡化路由計算,以及降低干擾,因此十分適合作為無線底層拓撲。Yao Graph 研究人員提出了許多Yao Graph的變種,如在GG圖上使用Yao Graph,在Yao Graph上使用GG 圖等,以減少Yao G

7、raph中的邊數(shù)并同時保持Spanner性質(zhì)。-Graph 與Yao Graph 非常相似。不同之處在于,Yao Graph在每個扇區(qū)中選擇最近的結(jié)點建立鏈路,而-Graph選擇在扇區(qū)中軸投影最短的結(jié)點建立鏈路。2.概率分析方法發(fā)展成熟的隨機圖理論不適合無線傳感器網(wǎng)絡(luò)。事實上,隨機圖假設(shè)任意兩個結(jié)點間的邊的存在與否是互相獨立的,這一假設(shè)不符合無線傳感器網(wǎng)絡(luò)的特點。為解決這個問題,研究人員提出了幾何隨機圖理論。在該理論中,結(jié)點按照某種概率密度分布在d維區(qū)域R中。研究人員研究了這種結(jié)點分布下的某些性質(zhì),諸如:到最近鄰居的最長鏈路,歐式最小生成樹中最長邊的長度,MST的總開銷。最近,研究人員使用幾何

8、隨機圖理論研究無線ad hoc網(wǎng)絡(luò)的某些基本的性質(zhì),如連通性。另外兩種理論是連續(xù)滲流(continuum percolation和占位理論(occupancy theory。在連續(xù)滲流理論中,結(jié)點以Poisson密度分布在二維平面中,如果結(jié)點間距離小于r則兩個結(jié)點相連。已經(jīng)證明,對于>0,至多以大概率存在一個無限階的組件(由連通的結(jié)點組成的集合稱為組件,組件的階是結(jié)點集合中結(jié)點的個數(shù)。但是,只存在一個無限階的組件不能保證網(wǎng)絡(luò)的連通性。事實上,可能存在許多(無限多結(jié)點不屬于這個大組件,這樣就導(dǎo)致不連通的網(wǎng)絡(luò)通信圖。因此,連通性與屬于大組件的結(jié)點占所有結(jié)點的比例相關(guān),這個比例又與滲流概率相關(guān)

9、。但是,目前還沒有關(guān)于滲流概率的顯式表達式。由于連續(xù)滲流理論的模型與ad hoc的網(wǎng)絡(luò)模型相吻合,因此連續(xù)滲流理論被用于分析ad hoc網(wǎng)絡(luò)的連通性。在占位理論中,假設(shè)n個球獨立地放入C個格子中。球放入格子中的放法由描述格子的某些屬性的隨機變量確定。占位理論的目標是確定當n和C 趨近無窮時這些變量的概率分布(極限概率分布。占位理論可以用于分析ad hoc網(wǎng)絡(luò)的連通性,可以抽象為把區(qū)域R分割成相同大小的rd個小區(qū)域(格子,確定在這種情況下每個格子中至少有一個結(jié)點(球的概率。概率方法研究的最重要的問題是臨界傳輸范圍(CTR問題,即結(jié)點都是同構(gòu)的,傳輸范圍相同,使網(wǎng)絡(luò)連通的最小傳輸范圍是多少。研究這

10、個問題的原因在于在無線傳感器網(wǎng)絡(luò)中廉價的無線通信部件不可能動態(tài)調(diào)整傳輸范圍。在無線傳感器網(wǎng)絡(luò)中,只能把所有結(jié)點的傳輸范圍設(shè)為相同的值。減少功耗、增加網(wǎng)絡(luò)容量的惟一辦法是把傳輸范圍設(shè)為保持網(wǎng)絡(luò)連通的最小值。最適合解決CTR問題的概率理論是幾何隨機圖理論。因為臨界傳輸范圍就是MST中的最長邊,從最長MST邊的概率分布中可以推導(dǎo)出CTR的概率解。但幾何隨機圖理論只適用于密集的ad hoc網(wǎng)絡(luò)。因為理論假設(shè)放置結(jié)點的空間是固定的,當結(jié)點個數(shù)趨于無窮時,結(jié)點的密度也趨于無窮。但在實際情況中,網(wǎng)絡(luò)的密度不可能很大。事實上,一個結(jié)點傳輸時,在它通信范圍內(nèi)的其他結(jié)點必須保持沉默。如果結(jié)點密度非常大,當一個結(jié)點傳輸時,許多結(jié)點都必須保持沉默,將降低整個網(wǎng)絡(luò)的容量。研究人員還用占位理論分析稀疏ad hoc網(wǎng)絡(luò)中保證連通性的臨界傳輸范圍問題。近年來拓撲控制技術(shù)已成為研究的熱點,目前在這個研究領(lǐng)域中還存在著許多問題。首先,用于建模無線傳感器