無線網絡功率最小化的分布式中繼選擇方法*

武　航，錢麗萍*，陳慶章，盧為黨（.浙江工業大學計算機科學與技術學院，杭州3003；.浙江工業大學信息工程學院，杭州3003）

?

無線網絡功率最小化的分布式中繼選擇方法*

武航1，錢麗萍1*，陳慶章1，盧為黨2
（1.浙江工業大學計算機科學與技術學院，杭州310023；2.浙江工業大學信息工程學院，杭州310023）

摘要：中繼協作已視作提高邊沿用戶能量有效性和服務質量的新型技術。因此，針對存在瑞利衰落的解碼轉發中繼網絡如何選擇中繼節點以最小化系統總功率的問題，提出了使用分布式拍賣算法選擇合適的中繼節點以最小化系統總傳輸功率。該算法首先通過信道傳輸功率的閉合表達式得到用戶節點和中繼節點的最小傳輸功率，然后根據分布式拍賣算法為用戶節點分配合適的中繼節點。仿真結果顯示用戶節點僅需要通過和中繼節點交換少量信息就可以選擇合適的中繼節點。

關鍵詞：無線網絡；中繼選擇；拍賣算法；多用戶多中繼

協作無線網絡通過使用中繼節點改善鏈路的吞吐量，擴大覆蓋范圍和降低傳輸功率［1-2］。這些中繼節點可以使用放大轉發AF（Amplify-and-For?ward）協議和解碼轉發DF（Decode-and-Forward）協議處理收到的信息［3-4］。如果使用DF，中繼節點將會首先解碼收到的信息，然后再重新編碼后轉發出去。如果使用AF，則中繼節點僅放大收到的信號后直接轉發出去。

目前，中繼選擇相關研究備受無線通信領域學者的關注［5-17］。這些研究主要是通過選擇合適的中繼節點以實現不同的網絡服務質量要求，如最大化信道容量［5］，最小化中斷概率［6］，最小化傳輸功率［7］等。Erwu Liu［8］等人結合比例公平調度算法和協作分集提出了比例公平協作算法，通過該算法可以選擇使系統吞吐量最大化的中繼節點。Amarasuriya［9］等人提出輸出閾值多中繼選擇（OT-MRS）機制，該機制可以選出一個滿足信噪比（SNR）要求的中繼節點集合。Atapattu［10］研究了在雙向轉發放大協作網絡基礎上，通過選擇合適中繼以最大化鏈路的最差信噪比。在文獻［11］中，作者根據信道協作時中斷概率的閾值推導出最優功率分配的閉合表達式。根據該表達式可以迅速選擇使傳輸功率最小的中繼節點。孫立旭［12］等人采用拉格朗日乘子法和最陡下降法，提出了在AF模式下基于信道統計特性的中繼選擇方法，該方法可以使系統的中斷概率最小。葉帆［13］等人提出在延時信道中利用過時的瞬時信道狀態信息輔助進行中繼選擇的新方案。張娜［14］等人提出一種根據即時信道信息選擇最優中繼的策略，通過引入固定退避時隙和改進的隨機退避時隙解決中繼選擇沖突問題。劉順蘭［15］等人提出一種雙向中繼選擇策略，該策略同時考慮中繼節點處的接收信噪比和中繼節點到目的節點的信道增益兩個因素來選擇最優中繼。雖然文獻［8-15］針對無線網絡中的不同優化目標提出了多種優化算法，但是這些算法主要針對單源多中繼網絡系統，而在實際應用中，多源多中繼網絡的中繼選擇更為普遍［16-18］。Upadhyay［16］等人使用功率最小化算法選擇合適的中繼節點。使用該算法選擇的中繼節點可以使全局傳輸功率最小。文獻［17］提出一種啟發式算法最小化中繼的功率消耗，實現綠色協作通信。曹儐［18］等人綜合考慮系統容量和系統總功率兩個方面，提出了一種基于能效（容量/發送功率）最大化的中繼分配算法，該算法首先優化各協作鏈路效能，然后以能效為權值，使用匈牙利算法為各個源節點分配中繼以最大化系統能效。雖然文獻［16-18］中的算法可以應用于多用戶多中繼網絡系統，但是由于這些算法是通過集中式實現，因此其對單個節點的計算能力要求較高。另外，負責集中式計算的節點由于功耗較大導致其生命周期較短，從而會使整個網絡系統過早死亡。

與現有工作不同，本文將研究在瑞利衰落信道下，兩跳DF中繼網絡如何選擇中繼節點以實現網絡總傳輸功率最小化。具體而言，本文首先根據各個信道的中斷概率閾值得出在滿足中斷概率要求的情況下，用戶節點和中繼節點的最小發送功率；然后使用分布式拍賣算法（DAA）為每個用戶節點選擇合適的中繼節點；最終得到的分配方案可以使系統的總傳輸功率最小。本文提出的算法一方面使用了滿足信道中斷概率時節點的最小發送功率，這對于優化系統總傳輸功率十分有益；另一方面通過分布式的方案實現算法，這就降低了對單個節點的硬件要求，使得算法更易實現。

1　系統模型

本文考慮一個具有瑞利衰落信道的多用戶多中繼網絡模型，如圖1所示。該模型包括N個用戶節點，M個中繼節點和一個共同的目的節點D，其中用戶節點個數N小于中繼節點個數M（即N

假設每個中繼節點有一個全向天線，能夠同時發送和接收數據。hi，j和hj，D分別表示從用戶節點i到中繼節點j和從中繼節點j到目的節點D的信道增益。對于瑞利衰落信道，hi，j和hj，D可以分別用gi，jfi，j和gj，Dfj，D代替。其中，gi，j和gj，D表示路徑增益，本文假設gi，j和gj，D是僅和距離相關的常數；fi，j和fj，D用來模擬瑞利衰落信道，本文假設fi，j和fj，D滿足均值為1的獨立指數分布。

圖1　系統模型

當用戶i向目的節點發送信息時，將會分兩步執行DF協議。首先，用戶i以功率pi發送信息xi，用戶i的最大發送功率設為SPi，max。然后，如果第j個中繼節點負責協作用戶i，則該中繼將會解碼收到的信息，在重新加密之后，以功率pj發送給目的節點D，中繼j的最大發送功率設為RPj，max。中繼j和目的節點D處的SNR分別為

式中：nj和nD分別表示中繼j和目的節點D處的噪聲功率。只有當中繼j和目的節點D處的SNR均滿足要求時，目的節點才能正確的解碼收到的信息。假設SNR的閾值為γ，那么用戶節點i選擇中繼j轉發信息時，整個鏈路的中斷概率為

因為本文已假設fi，j和fj，D滿足均值為1的獨立指數分布，所以該中斷概率可以進一步表示為

2　問題建模

對于一個具有N個用戶節點和M個中繼節點的無線中繼網絡，當用戶節點i選擇中繼節點j轉發信息時，整個鏈路的傳輸功率為pi+pj。因此，用戶節點選擇不同的中繼節點，對應的鏈路功率也不同。本文將研究如何為用戶節點分配中繼以使系統的總傳輸功率最小。假設鏈路的中斷概率閾值為β，則該問題可以描述為

約束條件：

式中：cij=1表示用戶i選擇中繼節點j，cij=0表示用戶i不選擇中繼節點j。保證每一個用戶可以選擇一個中繼節點進行協作傳輸，表示一個中繼節點最多被一個用戶選擇。

定義一個映射α表示從集合S={1，…，N}到集合R={1，…，M}的映射關系，當且僅當用戶i選擇中繼節點j時，α（i）=j。另外，將中斷概率Oij的表達式代入問題（4），同時使用Qij表示，其中和p*j分別表示用戶節點i和中繼節點j在滿足中斷概率情況下的最小傳輸功率，p*i和p*j的具體值將在下文給出。這樣就可以將該最小化問題轉換為一個最大化問題：

約束條件：

對于問題（5），當找到一個分配使每個用戶節點都有一個中繼節點且所有用戶所選的中繼節點都不相同時，如果該分配能夠使整個網絡系統的Qij之和最大，那么該分配就是使系統總傳輸功率最小的分配。

3　算法

3.1計算信道最小傳輸功率

在問題（5）中，用戶節點和中繼節點的發送功率是不確定的，因此Qij是未知的。當用戶節點i選擇中繼節點j時，在的條件下，兩者在滿足中斷概率要求時的最小傳輸功率之和p*i+p*j可以根據定理1求出；在的條件下，信道不能滿足最小中斷概率的要求，用戶節點i也就不可能通過中繼節點j和目的節點D通信，所以在這種情況下認為鏈路ij對應的權重Qij為無窮小。為了便于用戶節點選擇中繼，可以假設該鏈路對應的權重為根據該假設，若用戶節點i不能通過中繼j和目的節點D通信，則鏈路ij對應的權重要遠遠小于其他鏈路對應的權重，因此在最大化權重的前提下，用戶節點i就不會選擇中繼j進行協作傳輸。

反之，用戶節點i與中繼節點j的最小發送功率之和為，其中：

由于篇幅限制，本文不再對定理1進行證明，詳細的證明過程可以參考文獻［11］。根據定理1，每個用戶節點都可以知道從自身通過每個中繼節點到達目的節點所消耗的最小傳輸功率。因此，我們接下來將利用分布式拍賣原理設計中繼選擇算法。假設該網絡系統中的用戶節點和中繼節點可以互相收到對方的廣播，則用戶節點可以和中繼節點交換少量的信息。

3.2算法描述

本文所提出的中繼選擇算法主要是基于分布式拍賣理論。簡單而言，中繼節點首先計算每條鏈路在滿足中斷概率要求時的最小傳輸功率。然后定義表示中繼j的價格，定義表示用戶節點i選擇中繼j時的效益，根據中繼的價格，每個用戶節點選擇一個使其效益最大的中繼節點。算法的詳細步驟如下：

步驟1：在初始階段，每個用戶節點將自己的中斷概率需求以及最大發送功率廣播給每個中繼節點。中繼節點依據其感知到的信道增益和它的最大發送功率利用定理1計算各協作鏈路的最小傳輸功率，并將最小傳輸功率以權重Qij的形式通知相應的用戶節點。

步驟2：在t時刻，用戶節點i向中繼節點廣播其對所有中繼的出價priceij( )t。每個中繼節點j收到用戶廣播來的出價信息后，選擇最高出價作為自己的價格，然后將自己的價格price*j( )

t廣播給所有用戶節點。用戶節點i根據收到的廣播信息和本地存儲的中繼信息相比較，然后更新本地存儲的所有中繼j的價格：

所有用戶節點迭代執行步驟二到步驟四，直到整個網絡系統達到均衡狀態。所謂的均衡狀態是指每個用戶節點最終選擇的中繼節點都是使其效益最大的中繼節點，即滿足

由于用戶節點想要讓中繼節點為其服務時，需要向中繼節點出價，因此當多個用戶節點都選擇同一個中繼節點時，這些用戶節點需要互相競價。但是由于用戶節點可能僅請求將該中繼節點分配給它們卻不增加出價，這將導致競價行為無限進行下去。為了避免這種情況發生，規定用戶節點每次出價都必須至少增加ε，所以，如果最終的分配滿足

則也認為這是處于均衡狀態。

當迭代完成后，整個網絡系統處于均衡狀態，此時用戶節點所選擇的中繼節點可以使整個無線網絡的總傳輸功率最小。

3.3算法分析

在上述算法中，假設經過有限次迭代，網絡系統處于均衡時，第i個用戶節點所選擇的中繼為α （i），第j個中繼的價格為price*j，則該算法的時間復雜度及最終分配所對應的總傳輸功率和最優總傳輸的差值可分別由定理2和定理3得出。

定理2對于一個具有N個用戶節點，M個中繼節點的無線網絡，當算法迭代完成后，該算法的運行時間為

證明在上述算法中，如果一個中繼節點在k次競價中均被某一個用戶節點選為最優中繼，那么它的價格至少增加kε。因此，當k足夠大時，該中繼和那些沒有收到任何出價的中繼相比將會降低用戶節點的收益。當每個中繼至少收到一個出價，該算法將會結束。對于初始價格為0的情況，每個中繼的總迭代次數不會超過。如果每次迭代只有一個用戶出價，總迭代數不會超過的N倍。一次出價過程包含O（M）次

定理3對于N個用戶節點的網絡，當ε>0時，最終得到的總傳輸功率和最優的總傳輸功率差值DP∈(0，Nε]。

證明當迭代完成后，每個用戶節點所選擇的中繼均滿足公式（10），將N個式子相加可得

即

根據權重和鏈路功率的對應關系可知最終得到的總傳輸功率和最優的總傳輸功率差值DP∈(0，Nε]。

從下文仿真結果中可以看出，本文的算法經過數次迭代后可以很快達到收斂狀態。對于一些對功率要求不嚴格的網絡環境，可以進一步增大ε的取值，以加快收斂速度。另外，為了減小網絡開銷，本文的算法還可以通過集中式實現。首先用戶節點將中斷概率需求和最大發送功率發送給中繼節點，然后中繼節點計算出各個鏈路的權重并將權重和中繼的價格發送給目的節點。最后，目的節點根據這些信息在本地構建出整個網絡的虛擬拓撲結構，通過迭代執行更新，加價操作得出最優的分配方案。集中式實現雖然降低了網絡開銷，但是要求目的節點具有一定的計算能力，同時能夠負擔較大的功耗。

4　實驗結果與分析

本文考慮一個具有N個用戶節點，M個中繼節點和一個目的節點的多用戶多中繼無線網絡。所有的節點分布在一個500 m×500 m的區域，假設目的節點位于（250 m，250 m）處，中繼節點隨機分布在以（250 m，250 m）為圓心，內圓半徑50 m，外圓半徑100m的圓環中，用戶節點隨機分布在以（250 m，250 m）為圓心，內圓半徑100 m，外圓半徑250 m的圓環中。假設用戶節點和中繼節點以及中繼節點和目的節點之間的路徑增益gi，j和gj，D是和它們之間的距離有關的值，其中。所有用戶節點的最大發送功率為0.5 W，所有中繼節點的噪聲功率為0.1 μW，最大發送功率為1 W。另外，假設每條鏈路的中斷概率閾值為0.001，信噪比閾值為0.001。為了驗證該分布式拍賣算法的性能，本文進行了大量仿真實驗。本文首先將分布式拍賣算法與匈牙利算法［19］進行對比，然后將傳統網絡環境下（用戶節點和中繼節點的發送功率是相等的）分布式拍賣算法得出的系統總功率與考慮鏈路最小傳輸功率時的系統總功率進行對比，下面是實驗的結果和分析。

圖2是用戶節點數目小于中繼節點數目時（假設用戶節點數目比中繼節點數目少10個），本文所述算法和匈牙利算法迭代次數的對比圖。其中，橫坐標為用戶節點數目，縱坐標為算法迭代次數。

圖2　迭代次數對比（N

從圖2可以看出，無論ε=0.001還是ε=0.01，分布式拍賣算法的迭代次數明顯要小于匈牙利算法。隨著用戶數目的增加，匈牙利算法的迭代次數增加的較快，而同等情況下，分布式拍賣算法的迭代次數變化比較平緩。因此，分布式拍賣算法受網絡規模增大的影響較小。另外，隨著用戶節點數目的增加，算法的迭代次數并不是單調增加。這是因為算法的迭代次數除了和用戶節點數目相關，還與每條鏈路的傳輸功率有關。

圖3是當中繼節點數目為固定值（假設為110個）時，本文所述算法與匈牙利算法迭代次數對比圖。其中，橫坐標為用戶節點數目，縱坐標為迭代次數。從圖中可以看出，當中繼節點數目固定時，本文所述算法的迭代次數要遠小于匈牙利算法，并且隨著用戶數目的增加，迭代次數增幅很小。因此，本算法對于用戶節點數目小于中繼節點數目的網絡系統，能夠迅速收斂，快速找到合適的中繼節點。

圖3　中繼節點數目固定時迭代次數對比圖

圖4是當ε=0.001時和ε=0.01時，分布式拍賣算法得出的系統總功率和匈牙利算法得出的系統總功率的對比圖。其中，橫坐標為用戶節點數目（假設用戶節點數目比中繼節點數目少10個），縱坐標為最終傳輸功率。從圖4可以看出，分布式拍賣算法得出系統總功率曲線與匈牙利算法得出的系統總功率曲線基本重合，而且隨著ε的減小，兩者的誤差會更小。根據圖2~圖4可以發現，增大ε的值不僅會加快算法的收斂速度，也會增大最終分配的誤差，但是這種誤差比較小。因此，當對功率要求不是十分嚴格時，可以適當增大ε的取值以加快網絡的收斂。

圖4　分布式拍賣算法與匈牙利算法的最終總功率

在傳統的中繼選擇方案中，用戶節點i和中繼節點j的發送功率一般是相等的，而本算法則是令節點根據信道中斷概率選擇最小發送功率。根據定理1的證明［11］，當Oij=β時，用戶節點和中繼節點的發送功率相同（pi=pj），此時節點的發送功率不一定是滿足鏈路中斷概率的最小發送概率。下面將對比這種情況下的系統最優總功率與本文中考慮鏈路最小傳輸功率時的系統最優總功率。

圖5是當用戶節點i和中繼節點j使用相同的發送功率時的系統總傳輸功率與本文所述算法對應的系統總傳輸功率的對比圖。其中，橫坐標為用戶節點的數目（假設中繼節點數目固定為110），縱坐標為最終分配對應的總功率。從圖中可以看出，本文算法得出的最終總傳輸功率與匈牙利算法的最終總傳輸功率基本一致，而在傳統中繼選擇方案中，由于沒有使用鏈路的最小傳輸功率，因而得到的總傳輸功率和最優結果有一定差距。

圖5　分布式拍賣算法在傳統中繼選擇方案和考慮鏈路最小傳輸功率時的系統總功率對比

5　結論

本文首先針對存在瑞利衰落的多用戶多中繼無線網絡，根據各用戶的最小中斷概率要求得到所有用戶節點和中繼節點的最小發送功率。其次，用戶節點通過和中繼節點交換信息，使用分布式拍賣算法獨立的選擇中繼節點。最終所有用戶節點得到合適的中繼節點，該分配可以使整個無線網絡系統的總傳輸功率最小。

實驗結果顯示，分布式拍賣算法可以讓用戶節點在僅使用本地信息的情況下獨立選擇中繼節點。尤其是在用戶節點數和中繼節點數不等時，分布式拍賣算法可以使用較匈牙利算法更少的迭代次數選擇合適的中繼節點。另外，使用分布式算法不僅可以避免匈牙利算法中單個節點功率消耗過大的情況，還能夠充分利用網絡資源，延長網絡壽命。本文的分析結果可以為網絡架構提供重要的參考。

參考文獻：

［1］Yang S，Sheng Z，Mccann J，et al. Distributed Stochastic Cross-Layer Optimization for Multi-Hop Wireless Networks with Cooper?ative Communications［J］. IEEE Transactions on Mobile Comput?ing，2014，13（10）：2269-2282.

［2］Mo Z，Su W，Batalama S，et al. Linear-Mapping Based Coopera?tive Relaying Protocol Design with Optimum Power and Time Allo?cation［C］//Proc of the 2014 IEEE International Conference on Communications. Sydney，Australia：2014，4495-4500.

［3］Soliman S S，Beaulieu N C. Exact Analysis of Dual-Hop AF Maxi?mum End-to-End SNR Relay Selection［J］. IEEE Transactions on Communications，2012，60（8）：2135-2145.

［4］Bansal A，Bhatnagar M R，Hjorungnes A，et al. Low-Complexity Decoding in DF MIMO Relaying System［J］. IEEE Transactions on Vehicular Technology，2013，62（3）：1123-1137.

［5］Hasan Z，Bhargava V K. Relay Selection for OFDM Wireless Sys?tems under Asymmetric Information：A Contract-theory Based Ap?proach［J］. IEEE Transactions on Wireless Communications，2013，12（8）：3824-3837.

［6］Deng M Z K，Cao C. Relay Selection in Wireless Cooperative Net?works Using Decode-and-Forward Transmission［C］//Proc of the 2013 IEEE International Conference on Signal Processing，Com?munication and Computing. KunMing，China：2013，1-5.

［7］Zhang X L，Ji H，Li Y，et al. Energy Efficient Transmission in Re?lay-Based Cooperative Networks Using Auction Game［C］//Proc of the 2013 IEEE Wireless Communications and Networking Confer?ence. Shanghai，China：2013，1581-1585.

［8］Liu E W，Zhang Q Q，Leung K K. Relay-Assisted Transmission with Fairness Constraint for Cellular Networks［J］. IEEE Transac?tions on Mobile Computing，2012，11（2）：230-239.

［9］Amarasuriya G，Ardakani M，Tellambura C. Adaptive Multiple Re?lay Selection Scheme for Cooperative Wireless Networks［C］// Proc of the 2010 IEEE Wireless Communications and Networking Conference. Sydney，Australia：2010：1-6.

［10］Atapattu S，Jing Y D，Jiang H，et al. Relay Selection Schemes and Performance Analysis Approximations for Two-Way Networks［J］. IEEE Transactions on Communications，2013，61（3）：987-998.

［11］Qian L P，Wu Y，Chen Q Z. Transmit Power Minimization for Out?age-Constrained Relay Selection over Rayleigh-Fading Channels ［J］. IEEE Communications Letters，2014，18（8）：1383-1386.

［12］孫立悅，趙曉暉，虢明.基于中斷概率的協作通信中繼選擇與功率分配算法［J］.通信學報，2013，34（10）：84-91.

［13］葉帆，邱玲.延時信道信息下一種新AF中繼選擇算法［J］.中國科學院大學學報，2014，31（2）：243-248.

［14］張娜，陳曙.無線局域網MAC層協作通信改進方案［J］.傳感技術學報，2012，25（2）：283-288.

［15］劉順蘭，徐光建.一種改進的Two-Way中繼協作系統下的節點選取和功率分配策略［J］.傳感技術學報，2012，25（3）：388-401.

［16］Upadhyay M A，Mehta V J，Kothari D K. Power Minimization Al?gorithm in Multi Source Multi Relay Cooperative Wireless Network ［C］//Proc of the Nirma- University International Conference on Engineering. Ahmedabad，India：2012：1-4.

［17］Lin K Y，Liu K H. Green Cooperative Relaying in Multi-Source Wireless Networks with High Throughput and Fairness Provision?ing［C］//Proc of the Annual Summit and Conference of the Asia-Pacific Signal and Information Processing Association. Kaohsi?ung，Taiwan：2013：1-7.

［18］曹儐，段海霞，朱德利，等.協作通信系統中能效優化的中繼分配算法［J］.電子科技大學學報，2014，5（43）：807-812.

［19］Kuhn H W. The Hungarian Method for The Assignment Problem ［J］. Naval Research Logistics Quarterly，1955，2（1-2）：83-97.

武航（1989-），男，浙江工業大學在讀碩士研究生，主要研究方向無線網絡與通信，wuzjut@163.com；

陳慶章（1955-），男，浙江工業大學教授，博士，博士生導師，主要研究方向為傳感網絡、物聯網、計算機網絡及其應用、數據挖掘，qzchen@zjut.edu.cn；

錢麗萍（1981-），女，浙江工業大學副教授，博士，主要研究方向為無線網絡（包括物聯網、無線傳感網絡）資源優化分配理論與算法、認知無線電網絡、智能電網，lpqian@zjut.edu.cn；

盧為黨（1984-），男，浙江工業大學講師，博士，主要研究方向為無線網絡資源優化分配、認知無線電網絡，luweid@zjut. edu.cn。

An Distributed Deployment Algorithm in Mobile Heterogeneous Networks*

QIN Ningning1，2*，YU Yinghua1，WU Deen1
（1.School of Internet of Things Engineering，Jiangnan University，Wuxi Jiangsu 214122，China；2.Key Laboratory of Advanced Process Control for Light Industry Ministry of Education，Jiangnan University，Wuxi Jiangsu 214122，China）

Abstract：According to the maximum coverage problem of heterogeneous mobile sensor networks，a distributed de?ployment algorithm is proposed. By updating the target division subintervals based on the coordinates and sensing ranges of different nodes，the algorithm makes the node in every subinterval determine its velocity vector，which is related with the current location and remaining energy of the node and its delaunay neighbor nodes. Taking advan?tage of the mobility，the nodes would most likely to cover the target area. The simulation results show that this algo?rithm can improve the coverage rate and coordination speed of the network，as well as enhancing the balance of the residual energy of different nodes.

Key words：sensor networks；maximum coverage；target division subinterval；velocity vector；residual energy

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.017

收稿日期：2015-09-06修改日期：2015-10-10

中圖分類號：TN92

文獻標識碼：A

文章編號：1004-1699（2016）01-0088-07

項目來源：國家自然科學基金項目(61379122，61379023，61402416)；浙江省自然科學基金項目（LR16F010003，LQ15F010003）