基于移動—能量代價(jià)函數(shù)的無線自組織網(wǎng)絡(luò)路由策略研究*

劉半藤，周 瑩，陳友榮，王章權(quán)

(1.浙江樹人大學(xué)信息科技學(xué)院，杭州310015;2.浙江大學(xué)控制與工程學(xué)院，杭州310058)

基于移動—能量代價(jià)函數(shù)的無線自組織網(wǎng)絡(luò)路由策略研究*

劉半藤1，2*，周 瑩1，陳友榮1，王章權(quán)1

(1.浙江樹人大學(xué)信息科技學(xué)院，杭州310015;2.浙江大學(xué)控制與工程學(xué)院，杭州310058)

能量均衡技術(shù)一直是無線自組織網(wǎng)絡(luò)的熱點(diǎn)研究領(lǐng)域。在深入研究網(wǎng)絡(luò)信息傳輸特性的基礎(chǔ)上，提出了一種基于移動—能量代價(jià)函數(shù)的無線自組織網(wǎng)絡(luò)路由策略，并用于網(wǎng)絡(luò)信息傳輸。首先，本文考慮節(jié)點(diǎn)連通性、能量均衡性，提出了一種節(jié)點(diǎn)移動策略;然后，以傳輸路徑節(jié)點(diǎn)集合中的瓶頸節(jié)點(diǎn)剩余能量、傳輸鏈路數(shù)量作為準(zhǔn)則，建立以網(wǎng)絡(luò)節(jié)點(diǎn)為對象的能量代價(jià)函數(shù)?；谝苿印芰看鷥r(jià)函數(shù)的路由策略從鏈路層的決策轉(zhuǎn)移到節(jié)點(diǎn)層的決策。最后，采用MATLAB數(shù)值仿真該路由策略的性能，結(jié)果顯示:本文提出的移動—能量代價(jià)函數(shù)的路由策略既保持了原有路由優(yōu)化的精度，延遲網(wǎng)絡(luò)瓶頸節(jié)點(diǎn)能量下降速度，提高網(wǎng)絡(luò)生存時(shí)間。

能量代價(jià);生存時(shí)間;瓶頸節(jié)點(diǎn);動態(tài)規(guī)劃;路由策略

無線自組織網(wǎng)絡(luò)是一種由幾十乃至上百個(gè)具有感知、計(jì)算和通信能力的可移動節(jié)點(diǎn)組成，采用無線通信方式動態(tài)組成的對等網(wǎng)絡(luò)［1］。近些年，隨著傳感器技術(shù)、嵌入式計(jì)算技術(shù)、通訊技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)日趨成熟，使得無線自組織網(wǎng)絡(luò)的各種應(yīng)用逐漸成為可能，成為21世紀(jì)信息產(chǎn)業(yè)的重要支柱。在無線自組織網(wǎng)絡(luò)的各項(xiàng)技術(shù)中，路由策略和能量均衡技術(shù)一直是該研究領(lǐng)域的關(guān)鍵問題，制約著無線自組織網(wǎng)絡(luò)的進(jìn)一步發(fā)展，引發(fā)了國內(nèi)外專家學(xué)者的廣泛關(guān)注。在無線自組織網(wǎng)絡(luò)的實(shí)際應(yīng)用中，網(wǎng)絡(luò)節(jié)點(diǎn)采用電池供電，且通常要求網(wǎng)絡(luò)能持續(xù)工作幾個(gè)月乃至幾年時(shí)間。將網(wǎng)絡(luò)中第1個(gè)節(jié)點(diǎn)由于能量耗盡退出網(wǎng)絡(luò)的時(shí)間定義為網(wǎng)絡(luò)生存時(shí)間，網(wǎng)絡(luò)生存時(shí)間是評估無線自組織網(wǎng)性能的最重要指標(biāo)之一［2－3］。

因此，研究網(wǎng)絡(luò)能量均衡技術(shù)并將其應(yīng)用于網(wǎng)絡(luò)路由協(xié)議提高無線自組織網(wǎng)絡(luò)的生存時(shí)間顯得尤為關(guān)鍵與重要。近年來，國內(nèi)外專家學(xué)者針對能量路由開展了廣泛的研究。如文獻(xiàn)［4］中，作者提出了最小傳送能量路由算法。該算法選擇具有最小傳輸能量消耗的路徑將數(shù)據(jù)包從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn)，這種算法具有較好的能量有效性。但是由于能量有效的路徑上承擔(dān)過大的負(fù)載，容易造成能量有效的路由路徑提前死亡，從而其網(wǎng)絡(luò)生存時(shí)間并不高。文獻(xiàn)［5］中，作者提出了一種的能量均衡路由協(xié)議。在該協(xié)議中，通過在剩余能量大于某一閾值的節(jié)點(diǎn)集合中選擇具有最小傳輸能量消耗的節(jié)點(diǎn)作為信息傳輸?shù)南乱惶?jié)點(diǎn)。這樣可以平衡整個(gè)網(wǎng)絡(luò)的能量傳輸消耗，避免最短路由上的節(jié)點(diǎn)過早消耗盡能量，以實(shí)現(xiàn)一定程度上的能量消耗均衡性。文獻(xiàn)［6］中，作者提出了一種圖論算法，該算法試圖通過計(jì)算每一條路由的剩余能量水平，然后排除任何剩余能量水平高于最低能量路徑若干倍的路由。由于算法的性能取決于依靠經(jīng)驗(yàn)參數(shù)，因此算法并不能總是給出最優(yōu)的解決方案。文獻(xiàn)［7］中，針對網(wǎng)絡(luò)中某些關(guān)鍵節(jié)點(diǎn)過度消耗能量，致使網(wǎng)絡(luò)節(jié)點(diǎn)能耗分布不均，影響網(wǎng)絡(luò)的性能的缺陷，提出了一種基于博弈論的均衡路由協(xié)議，設(shè)計(jì)基于可靠度和節(jié)點(diǎn)的剩余能量的選擇路徑，解決節(jié)點(diǎn)能耗不均的問題，同時(shí)鼓勵節(jié)點(diǎn)參與協(xié)作。

在以上的文獻(xiàn)中，均沒有提到網(wǎng)絡(luò)節(jié)點(diǎn)的移動性會對網(wǎng)絡(luò)能耗所產(chǎn)生的影響。無線自組織網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)動態(tài)變化，節(jié)點(diǎn)無序移動性可能造成部分關(guān)鍵節(jié)點(diǎn)過早退出網(wǎng)絡(luò)，也可能使得網(wǎng)絡(luò)能量消耗更加均衡。為此，本文在分析網(wǎng)絡(luò)節(jié)點(diǎn)移動特性的基礎(chǔ)上，提出了一種基于移動—能量代價(jià)函數(shù)的路由策略。每次信息業(yè)務(wù)傳輸時(shí)，以傳輸路徑節(jié)點(diǎn)集合中的瓶頸節(jié)點(diǎn)剩余能量、信息鏈路數(shù)量作為代價(jià)函數(shù)，將路由協(xié)議中鏈路層的決策轉(zhuǎn)移到節(jié)點(diǎn)層的決策。

1 網(wǎng)絡(luò)節(jié)點(diǎn)移動策略研究

無線自組織網(wǎng)節(jié)點(diǎn)可以自由地在網(wǎng)絡(luò)區(qū)域內(nèi)移動，節(jié)點(diǎn)的無序移動性使得網(wǎng)絡(luò)計(jì)算變得更為復(fù)雜。因此，本文首先介紹一種節(jié)點(diǎn)移動策略，該策略可以提高網(wǎng)絡(luò)節(jié)點(diǎn)連通性與能量均衡性，同時(shí)也可以降低網(wǎng)絡(luò)搜索計(jì)算量。

假設(shè)有N節(jié)點(diǎn)隨機(jī)地分布于無線自組織網(wǎng)絡(luò)區(qū)域中，當(dāng)源節(jié)點(diǎn)s向目的節(jié)點(diǎn)d發(fā)送信息時(shí)，考慮信息中的1個(gè)比特B。傳輸比特B時(shí)，每個(gè)節(jié)點(diǎn)的坐標(biāo)可以表示為［xi(B)，yi(B)］， i=1，2，…，N。無線自組織網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有1個(gè)穩(wěn)定的通信半徑R［8］。因此，傳輸比特B時(shí)，無線自組織網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以用聯(lián)通矩陣C=［cij(B)］N×N和距離矩陣D=［dij(B)］N×N進(jìn)行表述。2個(gè)矩陣的元素含義如下:

傳輸比特 B時(shí)，節(jié)點(diǎn) i的剩余能量可以用 Ei(B)表示。假設(shè)在信息發(fā)送間隙，每個(gè)節(jié)點(diǎn)最大移動距離為L，L可以由網(wǎng)絡(luò)內(nèi)信息發(fā)送頻率確定。結(jié)合網(wǎng)絡(luò)連通性與節(jié)點(diǎn)剩余能量，本文提出了一種使用于無線自組織網(wǎng)絡(luò)的節(jié)點(diǎn)移動策略:①如果網(wǎng)絡(luò)中存在孤立節(jié)點(diǎn)i(即0)，應(yīng)該設(shè)計(jì)一種方法使該節(jié)點(diǎn)盡快進(jìn)入網(wǎng)絡(luò)連通區(qū)域。首先，尋找網(wǎng)絡(luò)節(jié)點(diǎn)中與此孤立節(jié)點(diǎn)最近的節(jié)點(diǎn)

如果dij＜L+R，則可以要求節(jié)點(diǎn)i向節(jié)點(diǎn)j移動min{L，dij－R}，節(jié)點(diǎn)j的移動策略不發(fā)生變化。如果dij≥2L+R，則可以要求節(jié)點(diǎn)i向節(jié)點(diǎn)j移動L，同時(shí)考慮節(jié)點(diǎn)j是否需要向節(jié)點(diǎn)i移動;如果節(jié)點(diǎn)j移動后LT上升，則節(jié)點(diǎn)j向節(jié)點(diǎn)i移動L，否則節(jié)點(diǎn)j的移動策略不發(fā)生變化。如果L+R＜dij＜2L+R，則可以要求節(jié)點(diǎn)i向節(jié)點(diǎn)j移動L，同時(shí)考慮節(jié)點(diǎn)j是否需要向節(jié)點(diǎn)i移動;如果節(jié)點(diǎn)j移動后LT上升，則節(jié)點(diǎn)j向節(jié)點(diǎn)i移動dij－R－L，否則節(jié)點(diǎn)j的移動策略不發(fā)生變化。

注意:即便節(jié)點(diǎn)k也是孤立點(diǎn)也沒有關(guān)系，節(jié)點(diǎn)i和節(jié)點(diǎn)k的相互移動會使得兩者不再是孤立點(diǎn)，提高網(wǎng)絡(luò)連通性。j。如果dij=mini≠kdik，說明節(jié)點(diǎn)j和節(jié)點(diǎn)i距離最近。

建立關(guān)于網(wǎng)絡(luò)連通性的指標(biāo)LT，用于評價(jià)節(jié)點(diǎn)i與節(jié)點(diǎn)j的相對移動是否會影響原有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的連通性。

②對于網(wǎng)絡(luò)中的非孤立節(jié)點(diǎn)，每個(gè)剩余能量高的節(jié)點(diǎn)都向節(jié)點(diǎn)剩余能量低的方向移動。對于其中的一個(gè)非孤立節(jié)點(diǎn)i而言，節(jié)點(diǎn)i可以感知到與其相鄰節(jié)點(diǎn)j的剩余容量，即Ej(B)。尋找到與節(jié)點(diǎn)i相鄰、剩余能量最低的節(jié)點(diǎn)考慮節(jié)點(diǎn)i是否需要向節(jié)點(diǎn)k移動。如果節(jié)點(diǎn)dik≤L，則可以要求節(jié)點(diǎn)i向節(jié)點(diǎn)k移動dik，同時(shí)節(jié)點(diǎn)k向節(jié)點(diǎn)i移動dik，形成節(jié)點(diǎn)i與節(jié)點(diǎn)k的位置互換，并不改變網(wǎng)絡(luò)連通性。如果節(jié)點(diǎn)dik＞L，考慮節(jié)點(diǎn)i與節(jié)點(diǎn)k的相互移動是否會影響網(wǎng)絡(luò)連通性的指標(biāo)LT。如果2個(gè)節(jié)點(diǎn)間相互移動并不影響LT，則可以要求節(jié)點(diǎn)i向節(jié)點(diǎn)k移動L，同時(shí)節(jié)點(diǎn)k向節(jié)點(diǎn)i移動L;否則，節(jié)點(diǎn)i和節(jié)點(diǎn)k并不發(fā)生移動。

本文所提出的移動策略如圖1所示。

圖1 節(jié)點(diǎn)移動策略

2 基于網(wǎng)絡(luò)能量代價(jià)函數(shù)的構(gòu)造

當(dāng)源節(jié)點(diǎn)s向目的節(jié)點(diǎn)d發(fā)送信息時(shí)，考慮信息中的一個(gè)比特B，由中間節(jié)點(diǎn)組成的集合中{vi(B)}，剩余能量最小的節(jié)點(diǎn)k也就是限制鏈路傳輸時(shí)間的關(guān)鍵瓶頸節(jié)點(diǎn)。節(jié)點(diǎn)k的確定過程如下:

動態(tài)源路由協(xié)議DSR是專家學(xué)者們提出的一種適用于無線自組織網(wǎng)絡(luò)信息傳輸?shù)穆酚蓞f(xié)議［9］。DSR路由協(xié)議的核心思想是以較少的鏈路數(shù)為代價(jià)將信息從源節(jié)點(diǎn)傳輸?shù)侥康墓?jié)點(diǎn)。該思想容易造成網(wǎng)絡(luò)中的部分節(jié)點(diǎn)由于業(yè)務(wù)過于繁忙而提早退出網(wǎng)絡(luò)，實(shí)際的網(wǎng)絡(luò)生存時(shí)間并不高。考慮瓶頸節(jié)點(diǎn)剩余能量Ek(B)的影響，本節(jié)提出了一種基于能量代價(jià)函數(shù)的構(gòu)造方式。當(dāng)源節(jié)點(diǎn)s向目的節(jié)點(diǎn)d發(fā)送信息時(shí)，每一個(gè)中間節(jié)點(diǎn)都將選擇能量代價(jià)函數(shù)最大的相鄰節(jié)點(diǎn)進(jìn)行信息傳輸。節(jié)點(diǎn)i能量代價(jià)函數(shù)fi(B)可以表達(dá)如下:

式中:fj(B)表示與節(jié)點(diǎn)i相鄰的可用于比特B傳輸?shù)南掠喂?jié)點(diǎn)j的能量代價(jià)函數(shù)。

為了防止出現(xiàn)多條剩余能量相同的節(jié)點(diǎn)，本文以傳輸路徑節(jié)點(diǎn)集合中的瓶頸節(jié)點(diǎn)剩余生存時(shí)間作為第一目標(biāo)、傳輸鏈路數(shù)量作為第二目標(biāo)。第二目標(biāo)的函數(shù)如下:

式中:hi(B)表示比特B從源節(jié)點(diǎn)發(fā)送到節(jié)點(diǎn)i所經(jīng)歷的鏈路數(shù)量，節(jié)點(diǎn)j是節(jié)點(diǎn)i的上游節(jié)點(diǎn)。

以上述代價(jià)函數(shù)進(jìn)行路徑搜索時(shí)，以能量代價(jià)fi(B)作為主要判別依據(jù)，鏈路數(shù)量代價(jià)hi(B)作為第二指標(biāo)進(jìn)行判別。該算法從源節(jié)點(diǎn)出發(fā)，每個(gè)中間節(jié)點(diǎn)都尋找下一跳的最優(yōu)節(jié)點(diǎn)，從而將鏈路層的決策轉(zhuǎn)化為節(jié)點(diǎn)層的決策。

該算法采用局部最優(yōu)的思想降低網(wǎng)絡(luò)計(jì)算量，但是并未考慮傳輸節(jié)點(diǎn)的能量消耗速率。通過式(5)、式(6)進(jìn)行修正，每個(gè)中間節(jié)點(diǎn)都需要判斷鏈路的能量消耗速率，并以此作為代價(jià)函數(shù)進(jìn)行路徑搜索［10］。因此，基于能量代價(jià)函數(shù)f*i(B)可以修正如下:

式中:E0表示無線自組織網(wǎng)絡(luò)中節(jié)點(diǎn)單次發(fā)送或者接收數(shù)據(jù)所消耗的能量，F(xiàn)i表示節(jié)點(diǎn)間兩兩通信一次所消耗的能量。

3 仿真分析

為了深入分析本文提出的基于移動—能量代價(jià)函數(shù)的路由策略對于無線自組織網(wǎng)絡(luò)生存時(shí)間、網(wǎng)絡(luò)容量產(chǎn)生的影響，本節(jié)采用MATLAB軟件對算法進(jìn)行數(shù)值仿真。

在一個(gè)300 m×300 m的矩形無線自組織網(wǎng)絡(luò)區(qū)域內(nèi)，隨機(jī)散布著80個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的通信半徑為50 m。對比網(wǎng)絡(luò)節(jié)點(diǎn)是否移動兩種策略對于網(wǎng)絡(luò)連通性的影響。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)按照本文所提出的移動策略移動時(shí)，網(wǎng)絡(luò)連通性隨時(shí)間而呈現(xiàn)上升狀態(tài)，而當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)處于靜止時(shí)網(wǎng)絡(luò)的連通性不發(fā)生任何變化，即為初始時(shí)刻的連通性61%。

假設(shè)無線自組織網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的初始剩余能量均與“1”，每個(gè)節(jié)點(diǎn)在每次處理信息時(shí)消耗0.001，不考慮網(wǎng)絡(luò)節(jié)點(diǎn)移動與待機(jī)所產(chǎn)生的影響。采用DSR路由協(xié)議，針對節(jié)點(diǎn)是否發(fā)生移動2種情況，無線自組織網(wǎng)絡(luò)瓶頸節(jié)點(diǎn)的能量變化如圖3所示。通過圖3可以發(fā)現(xiàn):固定式網(wǎng)絡(luò)中可能由于部分核心節(jié)點(diǎn)能量消耗過快，而使得網(wǎng)絡(luò)生存時(shí)間過低。

圖2 本文移動策略下，網(wǎng)絡(luò)連通性變化曲線

圖3 2種策略下，網(wǎng)絡(luò)瓶頸節(jié)點(diǎn)能量變化曲線

對比分析基于移動—能量代價(jià)函數(shù)的路由策略與DSR路由策略，分析網(wǎng)絡(luò)瓶頸節(jié)點(diǎn)隨仿真時(shí)間的變化趨勢如圖4所示。

圖4 2種路由協(xié)議瓶頸節(jié)點(diǎn)剩余能量的變化趨勢

通過圖4可以發(fā)現(xiàn):本文提出的基于移動—能量代價(jià)函數(shù)的路由策略可以有效地降低為網(wǎng)絡(luò)瓶頸節(jié)點(diǎn)能量下降速率，提高網(wǎng)絡(luò)生存時(shí)間。

4 結(jié)束語

在深入研究網(wǎng)絡(luò)節(jié)點(diǎn)移動特性的基礎(chǔ)上，本文提出了一種移動—能量代價(jià)函數(shù)的構(gòu)造方法，并用于指導(dǎo)網(wǎng)絡(luò)信息傳輸。首先，本文基于節(jié)點(diǎn)連通性、能量均衡性，提出了一種節(jié)點(diǎn)移動策略;然后，以傳輸路徑節(jié)點(diǎn)集合中的瓶頸節(jié)點(diǎn)剩余能量、傳輸鏈路數(shù)量作為準(zhǔn)則，建立以網(wǎng)絡(luò)節(jié)點(diǎn)為對象的能量代價(jià)函數(shù)。數(shù)值仿真結(jié)果顯示:本文提出的移動—能量代價(jià)函數(shù)的路由策略既保持了原有路由優(yōu)化的精度，也能提高網(wǎng)絡(luò)生存時(shí)間。

［1］ 劉杰，王玲，王杉，等.基于能量有效的逆向AODV路由協(xié)議研究［J］.計(jì)算機(jī)應(yīng)用研究，2015，32(6):1849－1851.

［2］ Vrinda Gupta，Rajoo Pandey.An Improved Energy Aware Distributed Unequal Clustering Protocol for Heterogeneous Wireless Sensor Networks［J］.Engineering Science and Technology，an International Journal，Volume 19，Issue 2，June 2016:1050－1058.

［3］ Zhang Deyu，Chen Zhigang，Zhou Haibo，et al.Energy-Balanced Cooperative Transmission Based on Relay Selection and Power Control in Energy Harvesting Wireless Sensor Network［J］.Computer Networks，2016，104(20):189－197.

［4］ 黃浩軍，尹浩，陳和平，等.無線Ad Hoc網(wǎng)絡(luò)能量感知地理路由協(xié)議研究進(jìn)展［J］.軟件學(xué)報(bào)，2014，(5):1061－1084.

［5］ 彭鐸，黎鎖平，楊喜娟，等.一種能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2014，27(12):1687－1691.

［6］ 蔣文賢.壓縮感知的能量異構(gòu)WSN分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2013，26(6):894－900.

［7］ Fatih Deniz，Hakki Bagci，Ibrahim Korpeoglu，et al.An Adaptive，Energy-Aware and Distributed Fault-Tolerant Topology-Control Algorithm for Heterogeneous Wireless Sensor Networks［J］.Ad Hoc Networks，2016，44:104－117.

［8］ Hao Xiaochen，Liu Weijing，Yao Ning，et al.Distributed Topology Construction Algorithm to Improve Link Quality and Energy Efficiency for Wireless Sensor Networks［J］.Journal of Network and Computer Applications，Available online，22 April 2016.

［9］ Huang Gaofei，Tu Wanqing.Optimal Resource Allocation in Wireless-Powered OFDM Relay Networks［J］.Computer Networks，2016，104: 94－107.

［10］Zhao Feng，Wei Lina，Chen Hongbin.Optimal Time Allocation for Multi-Antenna Wireless Powered Heterogeneous Sensor Network Communications under Imperfect CSI［J］.Signal Processing，2016，126:159－164.

劉半藤(1984－)，男，漢族，杭州余姚人，工科碩士，講師，主要研究方向?yàn)闊o線傳感網(wǎng)絡(luò)，信息融合技術(shù)，hupo3@ sina.com。

Research on the Routing Algorithm in MANETs Based on the Energy Cost Function*

LIU Benteng1，2*，ZHOU Ying1，CHEN Yourong1，WANG Zhangquan1
(1.College of Information Science and Technology，Zhejiang Shuren University，Hangzhou 310015，China; 2.College of Control Science and Engineering，Zhejiang University，Hangzhou 310058，China)

The energy balance technology is a hot research field of the wireless selforganizing network.After the further study of the network information transmission characteristics，a kind of wireless selforganized network routing strategy used for network information transmission is proposed based on mobile-energy cost function.At first，considering the node connectivity and energy balance，a node mobile strategy is carried out;then a energy cost function is designed With residual energy of transmission path bottleneck nodes and transmission link number as criterion，and the routing strategy is determined in node layer instead of link layer;at last，the numerical simulation is performed on MATLAB，the result shows the routing strategy proposed keep the original optimal routing precision，delay the network bottleneck node energy falling speed and improve the network survival time.

energy cost;survival life;bottleneck node;dynamic programming;routing strategy

TP393

A

1004－1699(2017)02－0302－04

C:7230

10.3969/j.issn.1004－1699.2017.02.023

項(xiàng)目來源:浙江省自然科學(xué)基金項(xiàng)目(LY15F030004);國家自然科學(xué)基金項(xiàng)目(61501403);浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目(2016C33038);浙江樹人大學(xué)校級科研項(xiàng)目(2104A11001)

2016－06－11 修改日期:2016－10－27