基于貪心算法的通信網絡能耗均衡分簇路由優化方法

阮玉生 屈慧潔

（1、廣西博聯信息通信技術有限責任公司，廣西 南寧530023 2、廣西教育學院 數學與信息科學學院，廣西 南寧530023）

針對通信網絡能耗均衡分簇路由方面的現有研究中，主要是圍繞如何降低通信網絡能耗均衡分簇路由協議端到端時延展開的，盡管能夠起到提升計算機通信網絡傳輸速率的作用，但在穩定性方面存在明顯不足[1]。因此，針對通信網絡能耗均衡分簇路由穩定性方面的優化成為此項內容的主流研究趨勢[2]。相比于普通路由，分簇路由受外界因素干擾較大，很容易出現斷鏈的現象，極大程度上增加了通信網絡能耗均衡分簇路由協議的通訊難度。針對傳統通信網絡能耗均衡分簇路由中存在的不足，貪心算法在研究中是指：求解某一具體問題過程中，一直在重復自身認為的最優選擇，即從某種角度上分析，能夠得出計算結果度量標準。基于此，有理由將貪心算法應用在通信網絡能耗均衡分簇路由優化中，本文基于貪心算法設計通信網絡能耗均衡分簇路由優化方法，致力于從根本上提高分簇路由投送成功率，進一步保證通信網絡能耗均衡分簇路由的穩定性。

1 貪心算法

貪心算法是針對某一局域范圍內最優解的計算，而并非基于全局角度考慮，但此種局部最優解的計算結果與整體最優解的求解結果較為接近。因此，貪心算法又被稱為貪婪算法，相對計算領域研究的一些其它計算算法，本文研究的此種算法在計算過程中，計算過程更為迅速、計算行為的發生更為簡便，以某一計算公式為例，此算法是按照計算公式的具體特點，將規范的步驟作為最優選擇，逐步完成計算，在選擇算法計算結果過程中，通常應以算法的優化度作為最佳選擇，且排除與之相關的可能性，算法省略了尋找最優解過程中所需要耗費的大量時間。因此在計算過程中，采用自頂部向下的計算方式，每執行一次算法計算，便需要將待處理的求解過程，近似的看作一個小規模循環計算過程，此過程被稱為貪心選擇。盡管在每一個求解步驟上，都可以得到一個近似結果的最優解，但在分解處理過程中，局部求解的答案不一定是全面計算過程的最優解。因此，對貪心算法的計算不需要對答案進行反復追溯。總之，將貪心算法認定為一個計算結果度量標準即可，在掌握局部最優解的基礎上，選擇其中的部分求解答案，將其相加處理后再導出，得到一個理論層面上的最優答案，此種計算過程與求解行為，便可稱為貪心算法。為此，本文基于貪心算法設計通信網絡能耗均衡分簇路由優化方法的具體研究內容，如下文所述。

2 通信網絡能耗均衡分簇路由優化

2.1 計算通信網絡能耗均衡分簇路由協議路徑指標

在本文優化設計的通信網絡能耗均衡分簇路由中，必須通過計算通信網絡能耗均衡分簇路由協議路徑指標，優化路徑中各鏈路指標[3]。本文選定的通信網絡能耗均衡分簇路由協議路徑指標包括：可靠性指標、穩定性指標以及相關性指標。可靠性指標能夠評判出通信網絡能耗均衡分簇路由的質量，可靠性指標又可細分為鏈路質量以及路徑質量，且這兩種指標可通過計算的方式加以表達，設鏈路質量可靠性指標的表達式為L，可得公式（1）。

公式（1）中，N 指的是鏈路正確接收通信信息的數量；X 指的是發送方發送的信息總數。通過公式（1），得出鏈路質量可靠性，以此反映通信網絡能耗均衡分簇路由的周期性傳播正確概率。在此基礎上，設路徑質量可靠性指標的表達式為P，可得公式（2）。

公式（2）中，K 指的是通信網絡能耗均衡分簇路由首次傳輸成功率。通過公式（1）、公式（2）可計算通信網絡能耗均衡分簇路由可靠性指標。針對穩定性指標的計算，本文采用鏈路失效估計模型，在通信網絡能耗均衡分簇路由中設置評估節點，以該節點為中心建立空間三維坐標軸。通過計算節點與通信網絡能耗均衡分簇路由傳輸運動速度向量之間的距離，判斷鏈路失效時間[4]。利用余弦定理此過程可通過計算的方式加以表達，設此目標函數為T，可得公式（3）。

公式（3）中，d 指的是通信網絡能耗均衡分簇路由通訊范圍半徑；R 指的是評估節點坐標；v 指的是通信網絡能耗均衡分簇路由傳輸運動速度；θ 指的是傳輸運動角度。通過公式（3）可知，當θ 大于90°時，節點與通信網絡能耗均衡分簇路由傳輸運動速度向量之間的距離較遠，鏈路失效時間短；當θ 小于90°時，節點與通信網絡能耗均衡分簇路由傳輸運動速度向量之間的距離較近，鏈路失效時間長。由此可見，T 值越大，通信網絡能耗均衡分簇路由穩定性越高；反之T 值越小，通信網絡能耗均衡分簇路由穩定性越低。通信網絡能耗均衡分簇路由相關性指標指的是可靠性與穩定性之前的關聯程度，一般情況下可通過相交路徑與不相交路徑表現，相交路徑表示通信網絡能耗均衡分簇路由受到外界干擾較大，存在斷鏈的危險性，導致通信網絡能耗均衡分簇路由的可靠性與穩定性低[5]。不相交路徑表示通信網絡能耗均衡分簇路由受到外界干擾較小，不存在斷鏈的危險性，導致通信網絡能耗均衡分簇路由的可靠性與穩定性高。

2.2 基于貪心算法分級處理通信網絡能耗均衡分簇路由

在計算通信網絡能耗均衡分簇路由協議路徑指標的基礎上，本文基于貪心算法分級處理通信網絡能耗均衡分簇路由[6]。將通信網絡能耗均衡分簇路由中所有路徑集合設為U，得出通信網絡能耗均衡分簇路由選路算法，如公式（4）所示。

公式（4）中，i 指的是通信網絡能耗均衡分簇路由中具有相同節點的路徑條數；j 指的是通信網絡能耗均衡分簇路由所有路徑集合中不相交路徑條數；γ 指的是通信網絡能耗均衡分簇路由選路最低可靠性；τ 指的是通信網絡能耗均衡分簇路由選路最低穩定性。通過公式（4），得出通信網絡能耗均衡分簇路由選路算法，并基于貪心算法建立鏈路，設定HELLO 信息傳播在一跳距離內傳播。再通過Topology Control 拓撲感知，根據拓撲狀態的實時變化，得出通信網絡能耗均衡分簇路由分級處理局部最優解。

2.3 實現通信網絡能耗均衡分簇路由優化

基于貪心算法分級處理通信網絡能耗均衡分簇路由后，以可靠性、穩定性最高為通信網絡能耗均衡分簇路由優化標準，選擇不相交路徑作為通信網絡能耗均衡分簇路由優化傳輸路徑[7]。并通過在多條不相交路徑中找到源節點作為中間節點，在負載均衡狀態下，實現通信網絡能耗均衡分簇路由傳輸。至此，完成基于貪心算法的通信網絡能耗均衡分簇路由優化方法設計。

3 實例分析

3.1 實驗準備

本文采用設計實例分析的方式，驗證優化的通信網絡能耗均衡分簇路由在實際應用中的適用性。為了保證實驗數據的準確性，整體實驗均在MATALB 平臺上進行，隨機選取一臺運行系統為XP 的計算機。定義的網絡節點通信范圍為（2.4*103）2m的二維矩形區域，打亂區域內數據。通信網絡參數設置，如下表1 所示。

表1 通信網絡參數設置

結合上述表1 中設定的參數數值，首先，采用本文基于貪心算法設計的通信網絡能耗均衡分簇路由，執行信息投送，通過黑盒工具-QAcenter 測得分簇路由投送成功率，設其為實驗組；而后，采用傳統通信網絡能耗均衡分簇路由，執行信息投送，通過黑盒工具-QAcenter 測得分簇路由投送成功率，設其為對照組。測得的分簇路由投送成功率越高，證明該通信網絡能耗均衡分簇路由的應用穩定性、可靠性越高。設置6 次實驗，記錄實驗結果，將實驗結果通過CPRS/DCMA 無線公網上傳至服務器Double PIV 1. 7 G 1 024 M RAM Double 80 G Disk。

3.2 實驗結果與分析

整理收集的數據，并將其繪制成折線圖，如圖1 所示。

圖1 分簇路由投送成功率對比折線圖

通過圖1 可知，本文設計的通信網絡能耗均衡分簇路由投送成功率明顯高于對照組，能夠實現對通信網絡能耗均衡分簇路由的優化，具有現實推廣價值。

4 結論

本文通過實例分析的方式，證明了設計通信網絡能耗均衡分簇路由在實際應用中的適用性，以此為依據，證明此次優化設計的必要性。因此，有理由相信通過本文設計，能夠解決傳統通信網絡能耗均衡分簇路由中存在的缺陷。但本文同樣存在不足之處，主要表現為未對本次分簇路由投送成功率測定結果的精密度與準確度進行檢驗，進一步提高分簇路由投送成功率測定結果的可信度。這一點，在未來針對此方面的研究中加以補足，以此為提高通信網絡能耗均衡分簇路由的通訊質量提供建議。