無線傳感器網絡的拓撲控制技術

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

應滿足的性質

拓撲控制算法的目標是通過控制結點的傳輸范圍使生成的網絡拓撲滿足一定的性質，以延長網絡生命周期，降低網絡干擾，提高吞吐率。

一般假設結點分布在二維平面上，所有結點都是同構的，都使用無向天線。以有向圖建模無線傳感器網絡，如果結點i的傳輸功率Pi大于從結點i到結點j需要的傳輸功率Pij，則結點i到結點j之間有一條有向邊。所有結點都以最大功率工作時所生成的拓撲稱為UDG圖(Unit Disk Graph)。

拓撲控制應使網絡拓撲滿足下列性質中的一個或幾個：

連通性—為了實現結點間的互相通信，生成的拓撲必須保證連通性，即從任何一個結點都可以發(fā)送消息到另外一個結點。連通性是任何拓撲控制算法都必須保證的一個性質。由UDG圖的定義可以知道，UDG圖的連通性是網絡能夠提供的最大連通性，因此一般假定UDG圖是連通的。所以，任何拓撲控制算法生成的拓撲都是UDG圖的子圖。

對稱性—指如果從結點i到結點j有一條邊，那么一定存在從結點j到結點i的邊。由于非對稱鏈路在目前的MAC協議中沒有得到很好的支持，而且非對稱鏈路通信的開銷很大，因此一般都要求生成的拓撲中鏈路是對稱的。

稀疏性—指生成的拓撲中的邊數為O(n)，其中n是結點個數。減少拓撲中的邊數可以有效減少網絡中的干擾，提高網絡的吞吐率。稀疏性還可以簡化路由計算。

平面性—指生成的拓撲中沒有兩條邊相交。由圖論可知，滿足平面性一定滿足稀疏性。地理路由協議是一種十分適合計算和存儲能力有限的無線傳感器結點的路由協議，它不需要維護路由表和進行復雜的路由計算，只需要按照一定的規(guī)則轉發(fā)消息。但當底層拓撲不是平面圖時，地理路由協議不能保證消息轉發(fā)的可達性。因此，當結點運行地理路由協議時，要求生成的拓撲必須滿足平面性。

結點度數有界—指在生成的拓撲中結點的鄰居個數小于一個常數d。降低結點的度數可以減少結點轉發(fā)消息的數量和路由計算的復雜度。

Spanner性質—指在生成的拓撲中任何兩個結點間的距離小于它們在UDG圖中距離的常數倍。
     
  研究方法

目前對拓撲控制的研究可以分為兩大類。一類是計算幾何方法，以某些幾何結構為基礎構建網絡的拓撲，以滿足某些性質。另一類是概率分析方法，在結點按照某種概率密度分布情況下，計算使拓撲以大概率滿足某些性質時結點所需的最小傳輸功率和最小鄰居個數。

1．計算幾何方法

該方法常使用的幾何結構有如下幾種：

最小生成樹(MST) 網絡拓撲是以結點間的歐式距離為度量的最小生成樹。結點的傳輸半徑設為與該結點相鄰的最長邊的長度。以MST為拓撲的網絡能保證網絡的連通性。由于在分布式環(huán)境下構造MST開銷巨大，一種折中的方法是結點采用局部MST方法設置傳輸范圍。

GG圖(Gabriel Graph) 在傳輸功率正比傳輸距離的平方時，GG圖是最節(jié)能的拓撲。MST是GG圖的子圖，GG圖也滿足連通性。

RNG圖(Relative Neighbor Graph) 其稀疏程度在MST和GG圖之間，連通性也在MST和GG圖之間，優(yōu)于MST，沖突干擾優(yōu)于GG圖，是兩者的折中。RNG圖易于用分布式算法構造。

DT圖(Delaunay Triangulation) UDG與DT圖的交集稱為UDel圖(Unit Delaunay Triangulation)。UDel圖是稀疏的平面圖，適合于地理路由協議、節(jié)能、簡化路由計算，以及降低干擾，因此十分適合作為無線底層拓撲。

Yao Graph 研究人員提出了許多Yao Graph的變種，如在GG圖上使用Yao Graph，在Yao Graph上使用GG圖等，以減少Yao Graph中的邊數并同時保持Spanner性質。

θ-Graph 與Yao Graph非常相似。不同之處在于，Yao Graph在每個扇區(qū)中選擇最近的結點建立鏈路，而θ-Graph選擇在扇區(qū)中軸投影最短的結點建立鏈路。

2．概率分析方法

發(fā)展成熟的隨機圖理論不適合無線傳感器網絡。事實上，隨機圖假設任意兩個結點間的邊的存在與否是互相獨立的，這一假設不符合無線傳感器網絡的特點。為解決這個問題，研究人員提出了幾何隨機圖理論。在該理論中，結點按照某種概率密度分布在d維區(qū)域R中。研究人員研究了這種結點分布下的某些性質，諸如：到最近鄰居的最長鏈路，歐式最小生成樹中最長邊的長度，MST的總開銷。最近，研究人員使用幾何隨機圖理論研究無線ad hoc網絡的某些基本的性質，如連通性。

另外兩種理論是連續(xù)滲流(continuum percolation)和占位理論(occupancy theory)。在連續(xù)滲流理論中，結點以Poisson密度λ分布在二維平面中，如果結點間距離小于r則兩個結點相連。已經證明，對于λ>0，至多以大概率存在一個無限階的組件(由連通的結點組成的集合稱為組件，組件的階是結點集合中結點的個數)。但是，只存在一個無限階的組件不能保證網絡的連通性。事實上，可能存在許多(無限多)結點不屬于這個大組件，這樣就導致不連通的網絡通信圖。因此，連通性與屬于大組件的結點占所有結點的比例相關，這個比例又與滲流概率相關。但是，目前還沒有關于滲流概率的顯式表達式。由于連續(xù)滲流理論的模型與ad hoc的網絡模型相吻合，因此連續(xù)滲流理論被用于分析ad hoc網絡的連通性。

在占位理論中，假設n個球獨立地放入C個格子中。球放入格子中的放法由描述格子的某些屬性的隨機變量確定。占位理論的目標是確定當n和C趨近無窮時這些變量的概率分布(極限概率分布)。占位理論可以用于分析ad hoc網絡的連通性，可以抽象為把區(qū)域R分割成相同大小的rd個小區(qū)域(格子)，確定在這種情況下每個格子中至少有一個結點(球)的概率。

概率方法研究的最重要的問題是臨界傳輸范圍(CTR)問題，即結點都是同構的，傳輸范圍相同，使網絡連通的最小傳輸范圍是多少。研究這個問題的原因在于在無線傳感器網絡中廉價的無線通信部件不可能動態(tài)調整傳輸范圍。在無線傳感器網絡中，只能把所有結點的傳輸范圍設為相同的值。減少功耗、增加網絡容量的惟一辦法是把傳輸范圍設為保持網絡連通的最小值。最適合解決CTR問題的概率理論是幾何隨機圖理論。因為臨界傳輸范圍就是MST中的最長邊，從最長MST邊的概率分布中可以推導出CTR的概率解。但幾何隨機圖理論只適用于密集的ad hoc網絡。因為理論假設放置結點的空間是固定的，當結點個數趨于無窮時，結點的密度也趨于無窮。但在實際情況中，網絡的密度不可能很大。事實上，一個結點傳輸時，在它通信范圍內的其他結點必須保持沉默。如果結點密度非常大，當一個結點傳輸時，許多結點都必須保持沉默，將降低整個網絡的容量。

研究人員還用占位理論分析稀疏ad hoc網絡中保證連通性的臨界傳輸范圍問題。

近年來拓撲控制技術已成為研究的熱點，目前在這個研究領域中還存在著許多問題。首先，用于建模無線傳感器網絡的模型過于理想化。為了得到更符合實際的量化結果，需要使用更真實的模型。其次，結點的分布假設過于理想化。一般的研究都假定結點是均勻分布的。雖然在某些情況下這種假設是合理的，但是在大多數情況下這樣的假設是過于理想化的。最后，安放無線傳感器的區(qū)域假設過于理想化。一般假設安放無線傳感器的區(qū)域是平坦的二維平面，沒有考慮地形的因素。