第三節 相對連通系數的近似定義

一 相對連通系數的近似定義

以上相對連通系數的定義比較適合于理論分析，但在實際應用時，由于問題的組合爆炸特性，在計算最大可能路徑數｜Ni｜時，會遇到難以克服的組合計數問題。另外，由于不同節點的｜Ni｜值相差懸殊，在應用時并不需要｜Ni｜的精確數值，只需對其數量級做大概估計即可。因此本節引入相對連通系數的近似定義來估計｜Ni｜的數量級，以避免求｜Ni｜精確值的復雜計算。

為了便于估計任一節點對目標節點的影響，需要把網絡轉換成以目標節點為根的一棵樹。這可以通過采用寬度優先搜索來實現。這樣，網絡中任一節點都對應一棵以該節點為根的子樹。該子樹可能產生的最大路徑數就表征了對應節點對目標節點的影響大小（見圖3-1）。

子樹可能產生的最大路徑數由兩方面因素決定，即子樹中總的邊數和子樹的“構型”（這里主要考慮子樹的層數和每層的邊數分布）。其中子樹的構型起著決定性的影響，在相同的邊數下，不同構型的子樹可能產生的最大路徑數往往有著巨大的差別。

為了量化子樹構型的這種差別，需要將最優和最差的構型作為度量的基準。其中最差構型很容易找到（如圖3-2所示）。

以上兩種最差構型子樹可能產生的最大路徑數都等于總邊數 m，即在最差構型的子樹中，可能產生的最大路徑數是隨邊數 m 線性增加的。

子樹的最優構型則不那么明顯，為簡化起見，下面分兩步來尋找最優構型。

①假設子樹的層數k已經確定，根據算術幾何不等式，有：

其中ai為第i層的邊數。

由上式可以看出，對具有m條邊的子樹來說，當每層邊數都相等時可能產生的路徑數最大，其最大值為（m/k）k。

②求最優層數k*：

假設每層邊數為x＝m/k，則子樹可能產生的路徑數為：

作變量代換，令x＝ey, ｜Ni｜可寫成：

對上式求極值，令：

求得當y＝1即x＝e時，子樹可能產生的路徑數最大，對應的最優層數為k*＝m/e。

綜合①、②可知，對具有m條邊的子樹來說，當層數k＝m/e，且每層邊數相等時，可能產生的路徑數最大，對應的最大路徑數｜ Ni｜ ＝em/e，即在最優構型的子樹中，可能產生的最大路徑數是隨邊數m指數增加的。

任一子樹構型可看作以上最優構型和最差構型的線性組合，其可能產生的最大路徑數由相應的線性增長項（最差構型）和指數增長項（最優構型）所占的比例決定。為了量化這一比例，本書引入子樹構型的特征向量的概念，具體如下。

定義：如果T為最大層數為m的一棵樹，那么T的特征向量是m維向量ST∈Rm，其中ST的各個分量分別為對應層的邊數。

兩棵樹的特征向量之間的距離與普通向量之間的距離不同，定義如下。如果u∈Rm, v∈Rn（m＜n），是兩棵樹的特征向量，u和v之間的距離記作dist（u, v），普通向量u′和v之間的距離為u′-v，其中u′是通過空位填零將u擴展到Rn所得向量，即有：dist（u, v）＝‖u′-v‖。

這樣，就可以通過特征向量之間的相對距離來度量一個子樹的構型與最優構型之間的偏離程度：

其中，λ是歸一化的任一構型到最優構型的相對距離；

ST是任一子樹構型的特征向量；

Smin是最差構型的特征向量（從兩種最差構型中任選一種作為標準即可）；

Smax是最優構型的特征向量。

從上式可以看出，當ST為最差構型時，到最優構型的相對距離最大，這時λ＝1，可能產生的最大路徑數為總邊數m；當ST為最優構型時，到最優構型的相對距離最小，這時λ＝0，可能產生的最大路徑數為em/e。

下面根據以上邊界條件從數學角度來推導任一子樹可能產生的最大路徑數的估計表達式。如前所述，子樹可能產生的最大路徑數由子樹總邊數和子樹的構型（這里等價于相對距離λ）兩方面因素決定，因此可設其為子樹邊數和到最優構型的相對距離的函數f（λ, m）。當邊數m固定時，子樹可能產生的最大路徑數主要由最優構型對應的指數增長項所占的比例決定，因此可認為這時f是隨λ按指數變化的，可設：

邊界條件可寫為：

解此方程組得：a＝ln m-m/e, b＝m/e, c＝1

由此得到任一子樹可能產生的最大路徑數的估計表達式為：

最后得到相對連通性系數的近似定義如下：

二 相對連通系數近似定義的遞歸計算方法

觀察相對連通系數近似定義的定義方法，發現其中表征節點對應子樹形狀的特征向量的計算具有遞歸嵌套的特點（如圖3-3所示）。

由此想到，可用子樹中下一級節點已有的特征向量來計算上一級節點對應的特征向量，這樣只用統計每個節點子樹當前層的邊數，從而可以設計遞歸算法一次求得所有節點相對目標節點的相對連通系數，算法的偽代碼如下（詳細實現代碼見附錄A）。

    Vector ComputeRCC（rootVertex）
    ｛
      //葉子節點處理
      If（rootVertex- ＞childNum＝ ＝0）｛
        //對于葉子節點子樹為空，因此相對連通系數為0
        rootVertex- ＞RCC＝0；
      saveRCCToFile（rootVertex- ＞RCC）；
      rootVertex- ＞edgeNum＝0；
      return 0；
    ｝
     //中間節點處理
    Else ｛
     //對于當前節點的所有下一級節點的特征向量求和，并統計下一級子樹邊數和
      For（i＝0; i＜rootVertex- ＞childNum; i+ +）｛
        extendVector+ ＝ComputeRCC（rootVertex- ＞childVertex ［i］）；
        rootVertex - ＞edgeNum + ＝rootVertex - ＞childVertex ［i］  - ＞
edgeNum；
    ｝

以上遞歸算法的算法復雜度與遍歷算法的復雜度相近，對于n個節點的網絡，求所有節點相對某一目標點的相對連通系數只需一次遍歷即可，時間復雜度是O（n）；即使要求一次求出所有節點相對網絡中所有目標點的相對連通系數，時間復雜度也只達到O（n2）。

采用以上遞歸算法計算相對連通系數還有以下好處。

無線傳感器網絡這一先進的通信和監測技術越來越多地被應用到應急物流管理中，在突發事件中受災地區通信基礎設施損毀的情況下，使用無線傳感器網絡可以在最短的時間內恢復通信，并實時監測配送道路的動態變化。基于相對連通系數的無線傳感器網絡節能路由算法的研究是這一領域今后的一個重要研究方向。在無線傳感器網絡路由算法中，通常需要監測網絡中各節點的通信負載狀況，及時進行動態均衡，以降低重要節點的能耗，提高無線傳感器網絡的整體壽命。相對連通系數可用來度量節點在網絡中承擔的通信任務的繁重程度，這時采用以上遞歸算法求相對連通系數就體現出其特別適合于無線傳感器網絡分布式計算結構的優點。