求解網絡編碼優化問題的混合啟發式算法*

徐志翔 楊余旺 郭利強 牛曉春 肖高權

（1.南京理工大學 南京 210094）（2.兵器淮海工業集團有限公司 長治 046000）（3.兵裝云箭集團有限公司 懷化 419503）

1 引言

A.Rhlswede等在2000年提出網絡編碼（Network Coding）的理論，其主要思想來源于圖論中著名的最大流最小割理論［1］。不同與傳統的網絡傳輸技術中中間節點僅負責轉發信息，網絡編碼賦予中間節點編碼和轉發的功能，即中間節點從各個輸入鏈路中獲取信息并進行編碼，然后把編碼后的數據傳輸給所有輸出鏈路［2］，更好地利用網絡帶寬，增大網絡吞吐量。但網絡編碼同時也帶來了編解碼的開銷。因此，如何在保證網絡編碼帶來優勢的同時，將隨之帶來的資源損耗將降低就成了一個研究的熱點問題。

網絡編碼優化［3］是指在給定的網絡拓撲下，針對優化的目標，在保證達到理論多播速率［4］的前提下，盡可能地降低網絡編碼的開銷。文獻［5］證明了網絡編碼優化問題是NP難問題，并使用傳統遺傳算法優化網絡編碼以求得最小編碼邊方案。但是隨著網絡拓撲的復雜度提升，算法運行時間倍增，得到解的質量下降。文獻［6］將模擬退火算法融合到網絡編碼優化領域，提出基于模擬退火遺傳算法的網絡編碼優化方案，該算法一方面采用了模擬退火的個體接收策略保證了種群多樣性，另一方面用網絡轉移矩陣指導遺傳操作，提高了收斂速度。文獻［7］將多目標優化理論和小生境遺傳算法融合到網絡編碼優化領域，提出基于多目標小生境遺傳算法的網絡編碼優化方案，在設計適應度函數的適合引入了多目標優化的概念，兼顧了最小化編碼邊數和帶寬利用率。雖然這些算法優化了傳統的遺傳算法，但是遺傳算法局部搜索能力不足的問題還是沒有得到有效解決。

在上述的研究基礎上，本文提出一種求解網絡編碼優化問題的混合啟發式算法，算法結合了遺傳算法并行的大規模搜索能力和局域搜索能力強的禁忌搜索算法。實驗表明，相比傳統GA算法，能有效得出最少編碼節點方案，加快了收斂速度，降低網絡編碼的開銷。

2 網絡編碼優化模型

2.1 網絡優化模型

為了方便研究，我們做出如下約定：

1）G=（V，E）表示一個單源有向無環網絡，其中V節點集合，E是邊集合，Rj是網絡的宿點，|R|表示宿點的個數，h表示最大理論傳輸容量，Ni是編碼節點標識。

2）G（V，E）中每條邊擁有單位傳輸速率，即單位時間內可傳輸單位數據。

3）采用隨機線性網絡編碼［8］，編碼操作是基于有限域的線性操作。對于每個節點v，分配一個節點編碼向量，標識該節點輸入鏈路的編碼情況。

4）將需要進額外編碼操作的節點稱為編碼節點，不需要進行編碼操作的節點稱為普通轉發節點。

5）輸出鏈路傳輸的信息是由各輸入鏈路上傳輸信息的基于有限域運算的線性組合，這種組合的系數所構成的向量稱為該鏈路的局部編碼向量。輸出鏈路的信息相對于源節點的各信息分量的一個映射系數稱為該輸出鏈路的全局編碼向量。

則對于宿點Rj的h條輸入信息流，傳輸的信息流向量可表示為公式：

目標函數：編碼節點的總數最小，即

約束條件：達到網絡的組播速率即

2.2 圖分解法

對一個網絡拓撲中的中間節點分為兩類，第一類為入度為1的中間節點，顯然這種節點是不需要編碼的。第二類為入度大于等于2的中間節點稱為匯點。針對匯點，當出度大于1后，無法確實其是否需要執行編碼操作以及需要編碼操作時如何編碼都是不可確定的，因此，我們參考文獻［9］提出的圖分解法。假設一個匯點有N個輸入，有M個輸出，其中N＞1，M＞1，則引入N個輸入輔助節點，M個輸出輔助節點，把匯點的N個輸入連接在對應的輸入輔助節點上，M個輸出流連接到對于的輸出輔助節點上，同時，每個輸入輔助節點連接所有的輸出輔助節點。具體如圖1所示。

圖1 圖分解法

2.3 節點的編碼

在有向圖G（V，E）中，針對所有匯點，我們為匯點的輸入鏈路分配二進制編碼向量，用來標識該輸入鏈路是否參與編碼運算。

如圖2，匯點v1入度為3，分別是i1，i2，i3，出度為1，所以該匯點的編碼向量用三位的二進制向量表示。當匯點v1的編碼向量為（1，0，0）時，表示只有鏈路i1參與編碼運算。若編碼向量為（1，1，1）時，則表示三條鏈路上的信息全部參與編碼運算。當整個網絡中的所有匯點的二進制編碼分配完畢后，整個網絡的信息流進而得以確定。

圖2 編碼向量為（1，0，0）的節點

3 遺傳算法

遺傳算法［10］是一種模擬自然界生物演化過程的計算模型，最先由美國的Holland教授提出。遺傳算法具有很好全局搜索能力，不會陷入類似梯度下降算法致使快速下降引發的局部收斂陷阱，是一種運算簡單、能有效解決問題的普適方法。但是，傳統的遺傳算法同樣存在不少缺點，例如局部搜索能力差，容易早熟，無法收斂于全局最優解。其主要起影響作用的遺傳操作主要有選擇算子、交叉算子、變異算子，下面我們對主要傳統的遺傳算法的主要算子和適應度函數進行說明并進行初步的優化。

圖3 傳統遺傳算法

3.1 選擇算子

本文算法中選擇算子采用輪盤賭選擇方法（Roulette Whell Selection）。輪盤賭選擇方法屬于一種回放式的隨機的采樣方法，它的基本思想就是個體適應度值在整個種群中適應度值總和的占比決定該個體進入到子代種群的概率。即產生一隨機數p，p∈（0，1），若

則個體i被選中，其中fitnessj為個體j的適應度值，N是種群的大小。

3.2 交叉算子

遺傳算法中，交叉率選擇對于遺傳算法的性能有著重要的影響。當交叉率過大時，不利于精英種群基因的傳承而當交叉率過小時，又不利于產生新解。因此，不同于傳統遺傳算法采用常數交叉率，本文算法采用自適應交叉率，每個個體都以一定的交叉率進行交叉運算，第i條個體的交叉率Pc的計算公式如下：

其中c1、c2是大于1的常系數，fitnessmax，是種群中最大的適應值，fitnessavg是最種群中平均適應度值。

針對網絡編碼的場景，交叉運算采用單元交叉，以節點的編碼系數為單元，即隨機地找出一個節點，交換兩個相互配對染色體的該節點的編碼系數。這種方法實現簡單且也能使得子代保留父代基本特征。

3.3 變異算子

同交叉算子，當變異算子的變異率過小時，不利于新解的產生，過大時，效果則趨向于隨機算法，失去原有的意義。因此，采用自適應變異率，每個個體都以一定的變異率進行變異運算，第i條個體的變異率Pc的計算公式如下

其中m1、m2是大于1的常系數。

變異是指對每個個體編碼串隨機地指定一位或者幾位基因位以一定的變異概率進行變異的運算。本文的變異運算采用取反運算代。變異運算對于改進遺傳算法的局部搜索的能力及維持種群多樣性，并防止早熟現象的出現都有比較好的效果。

3.4 適應度函數

在遺傳算法中，適應度函數用于評價染色體性能優劣的指標，需要結合具體求解問題來進行設計，是整個遺傳算法的核心。本算法除對滿足約束條件的解進行區分外，針對不滿足約束條件的解，根據能解碼的目標節點個數進行區分，對染色體i，其適應度函數設計如下：

其中G（i）是在i滿足約束條件下，能解碼的目的節點數，N是網絡總結點數，T（i）是指需要編碼的網絡節點，C1、C2為常數。

4 改進的遺傳算法

針對遺傳算法長于全局搜索短于局部搜索的特點，我們引進了禁忌搜索算法。禁忌搜索（Taboo Search TS）由Glover于1989年提出的一種基于局部搜索的算法［11～12］，是一種高效的逐步優化算法。相對于一般的局部搜索來說，為避免無效的重復搜索，禁忌算法模擬人類大腦中的記憶功能，引入了禁忌表的概念，通過禁忌表記錄近期訪問過的解，在一定時間內禁止訪問該解，進而更快地搜索更大范圍的解空間。禁忌搜索的偽代碼如表1所示。

表1 禁忌搜索算法偽代碼

禁忌搜索雖然搜索能力比較快且易于實現，但是它的性能優劣很大程度上依賴初始解的質量，如果初始解質量較差，也會容易陷入局部最優解。同時，禁忌算法作為一種串行算法，即它的運算過程是一個解向另外一個解轉化的過程，相對遺傳操作來說迭代次數多，計算時間長。而遺傳算法在初期迭代時，群體在解空間的分布還不是很穩定，如果在初期就是用禁忌局部搜索，會導致計算量過大，花費較大的時間成本，而且得到的解的質量也不高。

因此，本文提出了一種基于改進遺傳算法的網絡編碼節點最小化算法。該算法主要引入了禁忌搜索，將長于全局搜索的遺傳算法和長于局部搜索的禁忌搜索算法結合，即首先利用遺傳算法進行全局搜索，使群體中的個體相對穩定的分布在解空間的大部分區域，然后用禁忌搜索算法進行局部搜索以優化解的質量。該算法有效整合了傳統遺傳算法并行大范圍搜索能力和禁忌搜索優秀的局部搜索能力，大大降低了局部收斂的可能性，提高了全局收斂性能。其算法流程下所示。該混合策略的計算過程如下。

步驟1：設置相關參數，種群population，最大迭代次數T，禁忌搜索觸發持續代數S，當前迭代代數t=0，最大適應值持續代數BestfitConAlg=0；

步驟2：確定編碼方式，產生初始種群；

步驟3：計算每個個體的適應值，保存最大適應值的個體進入新的種群；

步驟4：t++；如果滿足觸發禁忌遺傳算法的條件，執行步驟9，否則執行步驟5；

步驟5：采用輪盤賭選擇進行選擇操作；

步驟6：采用自適應交叉概率選擇個體執行單元交叉操作；

步驟7：采用自適應變異概率選擇個體執行變異操作；

步驟8：如果滿足終止條件，停止運算，否則，轉而執行步驟4；

步驟9：t++；調用禁忌搜索算法，對種群的每個個體進行局部搜索；執行步驟4；

步驟10：如果滿足終止條件，停止運算，否則，轉而執行步驟8。

其中，觸發禁忌遺傳算法的條件：

當BestfitConAlg==S時，觸發一次禁忌搜索，每觸發一次S值降低一半，BestfitConAlg=0s；當最大適應值改變時，S恢復初始值，如圖4所示，假設初始S值為20。

圖4 S值變化圖

在0～10次中，最大適應值不變時，每執行一次禁忌算子，S值將為一半，當降至0時，即一直執行禁忌算子。當最大適應值改變時，S值恢復初始設定值。

5 仿真

為驗證改進算法的有效性，本文設計了仿真實驗，通過不同網絡拓撲和不同算法的實驗結果對比，驗證了本算法的有性能。

5.1 實驗環境與實驗數據集

本文仿真環境為Dell PC機，處理器為Intel（R）Core（TM）i5-3210M CPU@2.50GHz，內存為4.00GB，操作系統為64位Win7系統，對2～4層蝶形圖擴展網絡從算法有效性、運行時間及收斂性方面與傳統遺傳算法進行仿真比較分析。3層蝶形圖擴展網絡如圖5所示。

圖5 三層蝴蝶網絡模型

5.2 實驗結果與分析

表2給出了本文算法和傳統的遺傳算法在3組網絡拓撲結構下多次實驗得到的平均值，即在保證最大組播速率的前提下，所需編碼的最小節點數。從表中我們看出相對與傳統GA算法，本文算法能有效地得出最小編碼節點數。

表2 本文算法與傳統遺傳算法有效性驗證結果比較

為了分析和比較算法的收斂性能，實驗中記錄了三層蝴蝶模型的網絡拓撲下，群體最佳適應度的變化情況。從圖6我們看出，傳統的遺傳算法適應度增長速度比較緩慢，40代的時候發生突變，表明搜索到符合約束的解。80代的時候傳統的遺傳算法收斂于局部最優解。改進后的遺傳算法適應度增長速度明顯較快，但是在70代左右時仍然收斂于局部最優解。本文提出的混合禁忌改進遺傳算法適應值穩步上升，并在140代后達到最優解。這是因為本文算法引入了禁忌算法，彌補了遺傳算法局部搜索能力不足的缺點，有效結合了遺傳算法出色的并行大范圍搜索和禁忌搜索出色的局部搜索能力，提高了解的質量。

圖6 收斂性能比較

6 結語

本文在代數網絡編碼的框架下提出了網絡編碼優化模型，在此模型基礎上給出了一種求解網絡編碼優化問題的混合啟發式算法。本文算法是在傳統遺傳算法的基本之上，針對遺傳算法的不足引入了一些新的解決措施，減少無效的遺傳操作，提高了遺傳多樣性；設計了新的適應度函數，將沒有達到約束條件的解根據能解碼的目的節點的個數進行區分，提高了種群的多樣性。最后，引入了禁忌算法，改進了遺傳算法局部搜索能力不足的缺點，有效避免了算法的局部收斂。實驗結果表明，本文算法在達到理論多播速率的基礎上，能有效得出最小編碼節點數，降低網絡編碼的編解碼開銷，同時提高了收斂速度，解決了遺傳算法在網絡編碼應用中的陷入局部最優的問題，展現出的性能明顯優于傳統遺傳算法。