無線網(wǎng)絡(luò)功率最小化的分布式中繼選擇方法*

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

?

無線網(wǎng)絡(luò)功率最小化的分布式中繼選擇方法*

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

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

關(guān)鍵詞：無線網(wǎng)絡(luò)；中繼選擇；拍賣算法；多用戶多中繼

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

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

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

1　系統(tǒng)模型

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

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

圖1　系統(tǒng)模型

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

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

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

2　問題建模

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

約束條件：

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

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

約束條件：

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

3　算法

3.1計算信道最小傳輸功率

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

反之，用戶節(jié)點i與中繼節(jié)點j的最小發(fā)送功率之和為，其中：

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

3.2算法描述

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

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

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

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

所有用戶節(jié)點迭代執(zhí)行步驟二到步驟四，直到整個網(wǎng)絡(luò)系統(tǒng)達到均衡狀態(tài)。所謂的均衡狀態(tài)是指每個用戶節(jié)點最終選擇的中繼節(jié)點都是使其效益最大的中繼節(jié)點，即滿足

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

則也認為這是處于均衡狀態(tài)。

當?shù)瓿珊?，整個網(wǎng)絡(luò)系統(tǒng)處于均衡狀態(tài)，此時用戶節(jié)點所選擇的中繼節(jié)點可以使整個無線網(wǎng)絡(luò)的總傳輸功率最小。

3.3算法分析

在上述算法中，假設(shè)經(jīng)過有限次迭代，網(wǎng)絡(luò)系統(tǒng)處于均衡時，第i個用戶節(jié)點所選擇的中繼為α （i），第j個中繼的價格為price*j，則該算法的時間復雜度及最終分配所對應的總傳輸功率和最優(yōu)總傳輸?shù)牟钪悼煞謩e由定理2和定理3得出。

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

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

定理3對于N個用戶節(jié)點的網(wǎng)絡(luò)，當ε>0時，最終得到的總傳輸功率和最優(yōu)的總傳輸功率差值DP∈(0，Nε]。

證明當?shù)瓿珊?，每個用戶節(jié)點所選擇的中繼均滿足公式（10），將N個式子相加可得

即

根據(jù)權(quán)重和鏈路功率的對應關(guān)系可知最終得到的總傳輸功率和最優(yōu)的總傳輸功率差值DP∈(0，Nε]。

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

4　實驗結(jié)果與分析

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

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

圖2　迭代次數(shù)對比（N

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

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

圖3　中繼節(jié)點數(shù)目固定時迭代次數(shù)對比圖

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

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

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

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

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

5　結(jié)論

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

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

參考文獻：

［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］孫立悅，趙曉暉，虢明.基于中斷概率的協(xié)作通信中繼選擇與功率分配算法［J］.通信學報，2013，34（10）：84-91.

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

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

［15］劉順蘭，徐光建.一種改進的Two-Way中繼協(xié)作系統(tǒng)下的節(jié)點選取和功率分配策略［J］.傳感技術(shù)學報，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］曹儐，段海霞，朱德利，等.協(xié)作通信系統(tǒng)中能效優(yōu)化的中繼分配算法［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-），男，浙江工業(yè)大學在讀碩士研究生，主要研究方向無線網(wǎng)絡(luò)與通信，wuzjut@163.com；

陳慶章（1955-），男，浙江工業(yè)大學教授，博士，博士生導師，主要研究方向為傳感網(wǎng)絡(luò)、物聯(lián)網(wǎng)、計算機網(wǎng)絡(luò)及其應用、數(shù)據(jù)挖掘，qzchen@zjut.edu.cn；

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

盧為黨（1984-），男，浙江工業(yè)大學講師，博士，主要研究方向為無線網(wǎng)絡(luò)資源優(yōu)化分配、認知無線電網(wǎng)絡(luò)，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）