阮玉生 屈慧潔

（1、廣西博聯(lián)信息通信技術(shù)有限責(zé)任公司，廣西 南寧530023 2、廣西教育學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 南寧530023）

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

1 貪心算法

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

2 通信網(wǎng)絡(luò)能耗均衡分簇路由優(yōu)化

2.1 計(jì)算通信網(wǎng)絡(luò)能耗均衡分簇路由協(xié)議路徑指標(biāo)

在本文優(yōu)化設(shè)計(jì)的通信網(wǎng)絡(luò)能耗均衡分簇路由中，必須通過計(jì)算通信網(wǎng)絡(luò)能耗均衡分簇路由協(xié)議路徑指標(biāo)，優(yōu)化路徑中各鏈路指標(biāo)[3]。本文選定的通信網(wǎng)絡(luò)能耗均衡分簇路由協(xié)議路徑指標(biāo)包括：可靠性指標(biāo)、穩(wěn)定性指標(biāo)以及相關(guān)性指標(biāo)?？煽啃灾笜?biāo)能夠評(píng)判出通信網(wǎng)絡(luò)能耗均衡分簇路由的質(zhì)量，可靠性指標(biāo)又可細(xì)分為鏈路質(zhì)量以及路徑質(zhì)量，且這兩種指標(biāo)可通過計(jì)算的方式加以表達(dá)，設(shè)鏈路質(zhì)量可靠性指標(biāo)的表達(dá)式為L(zhǎng)，可得公式（1）。

公式（1）中，N 指的是鏈路正確接收通信信息的數(shù)量；X 指的是發(fā)送方發(fā)送的信息總數(shù)。通過公式（1），得出鏈路質(zhì)量可靠性，以此反映通信網(wǎng)絡(luò)能耗均衡分簇路由的周期性傳播正確概率。在此基礎(chǔ)上，設(shè)路徑質(zhì)量可靠性指標(biāo)的表達(dá)式為P，可得公式（2）。

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

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

2.2 基于貪心算法分級(jí)處理通信網(wǎng)絡(luò)能耗均衡分簇路由

在計(jì)算通信網(wǎng)絡(luò)能耗均衡分簇路由協(xié)議路徑指標(biāo)的基礎(chǔ)上，本文基于貪心算法分級(jí)處理通信網(wǎng)絡(luò)能耗均衡分簇路由[6]。將通信網(wǎng)絡(luò)能耗均衡分簇路由中所有路徑集合設(shè)為U，得出通信網(wǎng)絡(luò)能耗均衡分簇路由選路算法，如公式（4）所示。

公式（4）中，i 指的是通信網(wǎng)絡(luò)能耗均衡分簇路由中具有相同節(jié)點(diǎn)的路徑條數(shù)；j 指的是通信網(wǎng)絡(luò)能耗均衡分簇路由所有路徑集合中不相交路徑條數(shù)；γ 指的是通信網(wǎng)絡(luò)能耗均衡分簇路由選路最低可靠性；τ 指的是通信網(wǎng)絡(luò)能耗均衡分簇路由選路最低穩(wěn)定性。通過公式（4），得出通信網(wǎng)絡(luò)能耗均衡分簇路由選路算法，并基于貪心算法建立鏈路，設(shè)定HELLO 信息傳播在一跳距離內(nèi)傳播。再通過Topology Control 拓?fù)涓兄?，根?jù)拓?fù)錉顟B(tài)的實(shí)時(shí)變化，得出通信網(wǎng)絡(luò)能耗均衡分簇路由分級(jí)處理局部最優(yōu)解。

2.3 實(shí)現(xiàn)通信網(wǎng)絡(luò)能耗均衡分簇路由優(yōu)化

基于貪心算法分級(jí)處理通信網(wǎng)絡(luò)能耗均衡分簇路由后，以可靠性、穩(wěn)定性最高為通信網(wǎng)絡(luò)能耗均衡分簇路由優(yōu)化標(biāo)準(zhǔn)，選擇不相交路徑作為通信網(wǎng)絡(luò)能耗均衡分簇路由優(yōu)化傳輸路徑[7]。并通過在多條不相交路徑中找到源節(jié)點(diǎn)作為中間節(jié)點(diǎn)，在負(fù)載均衡狀態(tài)下，實(shí)現(xiàn)通信網(wǎng)絡(luò)能耗均衡分簇路由傳輸。至此，完成基于貪心算法的通信網(wǎng)絡(luò)能耗均衡分簇路由優(yōu)化方法設(shè)計(jì)。

3 實(shí)例分析

3.1 實(shí)驗(yàn)準(zhǔn)備

本文采用設(shè)計(jì)實(shí)例分析的方式，驗(yàn)證優(yōu)化的通信網(wǎng)絡(luò)能耗均衡分簇路由在實(shí)際應(yīng)用中的適用性。為了保證實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)確性，整體實(shí)驗(yàn)均在MATALB 平臺(tái)上進(jìn)行，隨機(jī)選取一臺(tái)運(yùn)行系統(tǒng)為XP 的計(jì)算機(jī)。定義的網(wǎng)絡(luò)節(jié)點(diǎn)通信范圍為（2.4*103）2m的二維矩形區(qū)域，打亂區(qū)域內(nèi)數(shù)據(jù)。通信網(wǎng)絡(luò)參數(shù)設(shè)置，如下表1 所示。

表1 通信網(wǎng)絡(luò)參數(shù)設(shè)置

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

圖1 分簇路由投送成功率對(duì)比折線圖

通過圖1 可知，本文設(shè)計(jì)的通信網(wǎng)絡(luò)能耗均衡分簇路由投送成功率明顯高于對(duì)照組，能夠?qū)崿F(xiàn)對(duì)通信網(wǎng)絡(luò)能耗均衡分簇路由的優(yōu)化，具有現(xiàn)實(shí)推廣價(jià)值。

4 結(jié)論

本文通過實(shí)例分析的方式，證明了設(shè)計(jì)通信網(wǎng)絡(luò)能耗均衡分簇路由在實(shí)際應(yīng)用中的適用性，以此為依據(jù)，證明此次優(yōu)化設(shè)計(jì)的必要性。因此，有理由相信通過本文設(shè)計(jì)，能夠解決傳統(tǒng)通信網(wǎng)絡(luò)能耗均衡分簇路由中存在的缺陷。但本文同樣存在不足之處，主要表現(xiàn)為未對(duì)本次分簇路由投送成功率測(cè)定結(jié)果的精密度與準(zhǔn)確度進(jìn)行檢驗(yàn)，進(jìn)一步提高分簇路由投送成功率測(cè)定結(jié)果的可信度。這一點(diǎn)，在未來針對(duì)此方面的研究中加以補(bǔ)足，以此為提高通信網(wǎng)絡(luò)能耗均衡分簇路由的通訊質(zhì)量提供建議。