能量高效的協(xié)作路由算法

凌 明，張大方，張 繼

（湖南大學 信息科學與工程學院，湖南 長沙410082）

0 引 言

無線傳 感器網(wǎng)絡 （wireless sensor networks，WSNs）的節(jié)點能量十分有限，且難以二次補充。如何降低或者平衡網(wǎng)絡的能耗，成為WSNs研究的一個重要方向。大量研究表明，協(xié)作通信對于降低傳輸功率、提高系統(tǒng)容量和擴大覆蓋范圍具有很好的效果。把協(xié)作通信技術應用于WSNs，成為提高網(wǎng)絡性能、降低能量開銷的有效方式。

協(xié)作通信是利用無線信道的廣播特性，通過共享網(wǎng)絡中其他節(jié)點的天線，形成虛擬的天線陣列，獲得性能增益。天線陣列可以減低共道干擾和多級衰落的影響，因此在一定的誤碼率和中斷概率下，協(xié)作可以降低發(fā)射功率。通過協(xié)作能夠有效解決WSNs中能耗效率問題。協(xié)作路由是聯(lián)合物理層的協(xié)作通信技術和網(wǎng)絡層的路由選擇技術的跨層路由選擇技術。結合WSNs的特點，設計一種低算法復雜度的能量高效的路由算法成為協(xié)作路由研究的熱點。

本文提出了一種能量高效的分布式、多跳、多中繼協(xié)作路由算法CWRN。算法利用無線通信信道的廣播特性，形成虛擬MIMO （multiple－input multiple－output），進行協(xié)作傳輸。仿真實驗結果表明，在保持誤碼率一定的情況下，新算法能夠降低能量開銷。

1 相關工作

文獻 ［1］提出了一種基于傳輸速率的協(xié)作路由算法，算法的主要思想是傳輸速率高的節(jié)點通過轉發(fā)數(shù)據(jù)包幫助傳輸速率低的節(jié)點傳輸數(shù)據(jù)。文章對于如何發(fā)現(xiàn)協(xié)作節(jié)點進行了詳細的描述。但文章只有單個協(xié)作節(jié)點參與傳輸，也沒有考慮到如何節(jié)省能量開銷。文獻 ［2］中當協(xié)作節(jié)點在經(jīng)過一段等待后，仍然沒有收到目的節(jié)點的確認信息，協(xié)作節(jié)點選擇重發(fā)，在任何時候只有單個協(xié)作節(jié)點去重發(fā)數(shù)據(jù)包。因此，文章的目的僅僅是降低誤碼率，同樣沒有考慮節(jié)省能量開銷問題。文獻 ［3－5］描述的是在每一跳的發(fā)送端和接收端中，都只有單個中繼節(jié)點參與協(xié)作傳輸。文獻 ［6］提出了一種基于MAC層的分簇集中式MIMO 系統(tǒng)，此協(xié)議中簇的形成類似于LEACH 協(xié)議。在路由路徑上，某個簇內的節(jié)點只發(fā)送數(shù)據(jù)包給下一簇的簇頭節(jié)點。這種集中式的結構需要消耗大量的能量去進行簇的維護。相比之下，分布式機制下簇的維護更容易，并且不會因為單節(jié)點失效影響整體網(wǎng)絡運行。因此，分布式機制更加適合于WSNs。

在網(wǎng)絡層方面，文獻 ［7］采用分簇機制，分析了兩個簇之間進行協(xié)作時的功率消耗，認為接收端由節(jié)點簇代替單個節(jié)點可以降低傳輸?shù)哪芎暮吞岣咄掏铝?。文獻 ［8］提出一種分布式的最小功率協(xié)作路由算法：MPCR 算法。算法在保證一定吞吐量的情況下選擇能量消耗最小的中繼節(jié)點進行協(xié)作傳輸，算法考慮的是吞吐量和發(fā)送功率的關系。文獻 ［9］在MPCR 算法的基礎上提出了MPSDF算法，分析了發(fā)射功率同中斷概率關系，推導出在一定誤碼率下的最小發(fā)射功率表達式。

文獻 ［10］提出了一種分布式的能量高效的協(xié)作路由算法：CWR 算 法，是 一 種 基 于MISO （multiple－input single－output）實現(xiàn)了MIMO 的協(xié)作路由算法。算法的復雜度低，并且能夠獲得MIMO 系統(tǒng)增益。在進行中繼選擇時考慮了備選中繼到上一跳以及備選中繼到下一跳的信道狀況。算法可以采用多中繼進行傳輸，但是并沒有對各跳中繼節(jié)點個數(shù)進行研究。

2 算法介紹

本文提出的協(xié)作路由算法CWRN 是一種采用多輸入單輸出 （MISO）實現(xiàn)多輸入多輸出 （MIMO）的多跳、多中繼協(xié)作路由算法。協(xié)作模型如圖1所示，形成了一種虛擬MIMO 系統(tǒng)，并進行協(xié)作傳輸。協(xié)議中，協(xié)作中繼采用放大轉發(fā)的方式轉發(fā)數(shù)據(jù)，在接收端采用最大合并比 （maximal ratio combining，MRC）技術合并信號。分簇機制已被證明能夠提高系統(tǒng)性能和降低傳輸功率，本協(xié)議也采用分簇機制組織協(xié)作節(jié)點。此外，我們還假設信道狀態(tài)信息（channel state information，CSI）是完全的，同時不考慮傳輸過程中的同步問題。

2.1 路由的兩個階段

如圖1所示，整個協(xié)作路由分成兩個階段：路由階段和中繼選擇階段。路由階段，通過AODV 協(xié)議尋找一條由源節(jié)點到目的節(jié)點的路徑最短的單徑路由；中繼選擇階段，以單徑路由上的每個節(jié)點為簇頭，招募它們的鄰居節(jié)點為備選中繼節(jié)點，確定中繼節(jié)點。AODV 協(xié)議是無線自組網(wǎng)按需平 面距離向 量 路 由協(xié) 議 （Ad－h(huán)oc on－demand distance vector routing，AODV），我們對AODV 協(xié)議進行了一些修改，加入了能量因素，并把鏈路所需的傳輸功率作為該鏈路的鏈路代價。我們假設簇間距離要遠大于簇內節(jié)點的距離，因而，簇頭節(jié)點能夠招募到其附近的鄰居節(jié)點作為中繼節(jié)點。

圖1 協(xié)作模型

圖2為中繼選擇階段的過程圖。在路由過程中，中繼選擇階段分為5個步驟。如圖2所示的場景中，需要確定簇頭節(jié)點5所在的第k 跳簇的中繼節(jié)點。中繼選擇的第一步：發(fā)送端簇頭節(jié)點2發(fā)送一個請求招募包 （request－to－recruit packet）給接收端簇頭節(jié)點5，包括發(fā)送端簇頭ID、接收端簇頭ID、sink節(jié)點ID、NAV field；第二步：簇頭節(jié)點5廣播招募包 （recruit packet）給它的鄰居節(jié)點，所有收到招募包的鄰居定義為候選中繼階段，招募包包括發(fā)送端簇頭ID、接收端簇頭ID、最大的應答時間T；第三步：所有的候選中繼計算鏈路代價并發(fā)送同意包 （grant packet）給簇頭節(jié)點，鏈路代價包括兩個部分：發(fā)送端簇內節(jié)點到候選中繼鏈路代價的算術平均、以及候選中繼到接收端簇內節(jié)點到候選中繼鏈路代價的算術平均。例如，節(jié)點4需計算鏈路 ［1，4］、［2，4］、 ［3，4］和 ［4，8］的能量開銷，即 （C1，4＋C2，4＋C3，4）／3＋C4，8。類 似 的，節(jié) 點6 計算鏈路 ［1，6］、 ［2，6］、 ［3，6］和 ［6，8］即（C1，6＋C2，6＋C3，6）／3＋C6，8。各節(jié)點間鏈路能量開銷情況在路由階段獲取；第四步：簇頭節(jié)點根據(jù)簇間物理位置信息和鏈路代價確定中繼節(jié)點個數(shù)mk并選定中繼節(jié)點ID，發(fā)送清除包 （clear packet）給候選中繼及前一跳簇頭節(jié)點。選定鏈路代價最小的前mk個為k 跳的中繼節(jié)點，同意的候選中繼節(jié)點數(shù)小于mk時則全部同意的候選中繼節(jié)點為k 跳的中繼節(jié)點；清除包包括確定中繼節(jié)點個數(shù)mk、選定中繼節(jié)點ID 以及更新的NAV 值；第五步：發(fā)送端簇頭發(fā)送確認包 （confirm packet）給它的簇內節(jié)點，包含下一跳接收端的節(jié)點ID、發(fā)送功率Pt、同步時間。傳輸功率為發(fā)送功率Pt除以發(fā)送端節(jié)點個數(shù)（mk＋1），mk為第k 跳中繼節(jié)點個數(shù)。

2.2 鏈路代價計算

圖2 中繼選擇階段

2.3 中繼節(jié)點個數(shù)的確定

通過大量的實驗，我們發(fā)現(xiàn)簇間距離比較小時，減少中繼節(jié)點個數(shù)總能量更有效，當距離變大時，增加中繼節(jié)點個數(shù)總能量更有效。產生這種現(xiàn)象的主要原因是：簇間距離大時，中繼信道同時出現(xiàn)衰落的概率大，增加中繼個數(shù)，能提高接收信號的信噪比，這時多個中繼參與協(xié)作的性能更好；而距離小時，如果采用多個中繼協(xié)作，信道間相互干擾等原因會導致頻譜利用率低，減少中繼節(jié)點個數(shù)反而性能更好。

2.4 模型分析

3 算法分析

根據(jù)以上公式分析包錯誤率Pf：假設Pt＝1 W ，γ ＝3，跳數(shù)i＝10，Pη＝10－10w，包的長度為1000bits，當n＝2，Pf＝0.0095；當n＝3，Pf＝0.0028；當n＝5，Pf＝0.0011；而當n＝7時，Pf＝0.0017。計算結果表明中繼節(jié)點數(shù)并不是越多越好，存在一個優(yōu)化值。

4 仿真實驗及結果

在本節(jié)，我們通過同CWR 算法相比較，對NCWR 算法的能耗情況進行仿真實驗。實驗場景是在一個400×400的空間內，隨機散布50 個節(jié)點，節(jié)點的通訊半徑是150米，鄰居半徑是50米，各節(jié)點的初始能量為0.5，數(shù)據(jù)包長度為1KB，γ＝3。通過兩組實驗分析新算法的性能。

圖3為能耗對比圖，橫坐標代表數(shù)據(jù)量，縱坐標代表剩余能量，此處為所有節(jié)點的平均剩余能量。數(shù)據(jù)表明，在誤碼率一定的情況下，隨著傳輸數(shù)據(jù)量的增加，NCWR相比CWR 算法在能耗方面節(jié)省6.41%以上。如圖3所示，在原算法m＝1時，能耗節(jié)省32.15%，當m＝2時，節(jié)省14.71%，當m＝3時，節(jié)省8.74%，當m＞＝4時，節(jié)省6.41%。m＞＝4時，在此節(jié)點密度下，簇頭沒有更多的鄰居節(jié)點可以招募，參與傳輸?shù)墓?jié)點不變?？梢钥闯鲂滤惴芎谋菴WR 算法能耗有所減低，主要原因是新算法參與協(xié)作的中繼節(jié)點數(shù)隨著簇間距離的增加而增多，較多的中繼節(jié)點數(shù)在距離增加的情況下能夠獲得增大的分集增益，從而減少傳輸端能量開銷。

圖3 能耗對比

圖4為中繼節(jié)點個數(shù)相同時兩種算法的能耗情況，當CWR算法中m＝2時，選擇兩種算法的參與協(xié)作的中繼個數(shù)相同的鏈路進行實驗。如圖4，此種情況下，NCWR 能耗節(jié)省15.46%。原因是新中繼選擇要更優(yōu)，此外通過優(yōu)化中繼節(jié)點的分配也可以節(jié)省能耗。

圖4 中繼個數(shù)相同時能耗對比

5 結束語

本文提出了一種能量高效的協(xié)作路由算法，通過MISO實現(xiàn)了MIMO，算法的復雜度較低，但可以獲得較高的協(xié)作分集增益。對中繼選擇時中繼選擇方式和中繼節(jié)點個數(shù)進行了研究，提出一種基于簇間物理距離的中繼節(jié)點個數(shù)確定算法，在相對簇間距離增大時，選擇較多的中繼節(jié)點參與協(xié)作傳輸，相反，則選擇較少的中繼節(jié)點個數(shù)。實驗結果表明新算法在能耗方面有所改善。本算法性能的提高在節(jié)點均勻分布的網(wǎng)絡并不明顯。

下一步工作是對多跳、多中繼網(wǎng)絡場景下最小功率進行研究，設計一種適合節(jié)點均勻分布的算法，并使得能耗進一步降低。

［1］Korakis T，Narayanan S，Bagri A，et al.Implementing a cooperative MAC protocol for wireless LANs［C］／／IEEE International Conference on Communications，2006：4805－4810.

［2］Khandani，Amir Ehsan.Cooperative routing in static wireless networks［J］.IEEE Transactions on Communications，2007，55 （11）：2185－2192.

［3］Hunter Todd E，Aria Nosratinia.Diversity through coded cooperation［J］.IEEE Transactions on Wireless Communications，2006，5（2）：283－289.

［4］Ibrahim，Ahmed S.SPC12－5：Relay selection in multi－node cooperative communications：when to cooperate and whom to cooperate with［C］／／Global Telecommunications Conference，2006.

［5］Dehghan M，Ghaderi M，Goeckel D L.On the performance of cooperative routing in wireless networks ［C］／／IEEE Conference on Computer Communications Workshops，2010：1－5.

［6］Yuan Y，Chen M，Kwon T.A novel cluster－based cooperative MIMO scheme for multi－h(huán)op wireless sensor networks ［J］.EURASIP Journal on Wireless Communications and Networking，2006 （2）：38－38.

［7］Vardhe K，Reynolds D，Woerner B D.Joint power allocation and relay selection for multiuser cooperative communication［J］.IEEE Transactions on Wireless Communications，2010，9（4）：1255－1260.

［8］Ibrahim A，Han Z，Liu K J R.Distributed energy－efficient cooperative routing in wireless networks［J］.IEEE Transactions on Wireless Communications，2008，7 （10）：3930－3941.

［9］Sheng Z，Ding Z，Leung K K.Distributed and power efficient routing in wireless cooperative networks ［C］／／IEEE International Conference on Communications，2009：1－5.

［10］Elhawary M，Haas Z J.Energy－efficient protocol for cooperative networks［J］.IEEE／ACM Transactions on Networking，2011，19 （2）：561－574.

［11］Chen G，Alnatouh O，Ge L，et al.Performance analysis of four relays selection scheme for cooperative networks ［C］／／11th International Conference on Information Science，Signal Processing and their Applications，2012：137－140.

［12］Jiang H，Zhang S，Zhou W.Energy－efficient distributed relay selection based on statistical channel state information ［M］.Wireless Internet.Berlin：Springer Berlin Heidelberg，2012：388－399.