一種結合威望的D2D通信中繼選擇算法

王汝言， 繆 懿， 閆俊杰

(1. 重慶郵電大學 通信與信息工程學院，重慶 400065；2. 重慶高校市級光通信與網絡重點實驗室，重慶 400065)

一種結合威望的D2D通信中繼選擇算法

王汝言1,2， 繆 懿1,2， 閆俊杰1,2

(1. 重慶郵電大學 通信與信息工程學院，重慶 400065；2. 重慶高校市級光通信與網絡重點實驗室，重慶 400065)

為了使終端直通通信能夠公平有效地選擇中繼節點，提出了一種基于威望的中繼選擇算法．利用威望從社會域的角度描述了設備作為中繼的意愿和能力; 同時在物理域分析了設備之間在不同傳輸模式下的數據傳輸情況; 采用博弈論的方法在候選中繼設備中選出適合的中繼，避免了社會關系弱、剩余能量低的設備被選作中繼．結果表明，與隨機選擇算法和最大吞吐量算法相比，該算法提高了系統的吞吐量、終端直通鏈路的覆蓋率以及中繼選擇的合理性．

終端直通;中繼;威望;吞吐量

從2015年到2020年，全球移動數據流量將增長近8倍．更多的數據流量將會從蜂窩網絡上卸載下[1]，即需要利用新技術分流基站的數據流，減輕基站負擔．第三代合作伙伴計劃(the 3rd Generation Partnership Project，3GPP)在R12版本中為長期演進(Long Term Evolution，LTE)引入了終端直通(Device-to-Device，D2D)通信技術，以解決近距離服務的使用場景[2]．其通信過程與傳統通信明顯不同，當兩個通信設備在空間上距離比較近時，設備之間可以不通過基站而直接傳輸數據，其中直接傳輸數據使用的頻譜資源是蜂窩小區的授權頻譜資源．引入D2D通信技術后可以帶來一系列的益處，例如，大幅提升蜂窩小區的系統容量、網絡可容納用戶數以及頻譜效率[3]．

由于D2D通信是短距離通信，其有效通信覆蓋面積有限，許多應用場景下兩個用戶并不在直接通信范圍內，若仍采用單跳通信模式，則通信鏈路質量會較差甚至中斷．因此可以考慮采用多跳的通信模式，即選擇適合的用戶作為中繼節點進行D2D中繼通信[4]．此種方式可以擴大D2D通信的覆蓋面積，減輕基站的負載，進而優化整個網絡的傳輸容量和功耗．

目前，因為中繼技術的潛在優勢，許多關于D2D通信的研究都已將其引入．文獻[5]研究了包含D2D通信的蜂窩網中基站的最佳調度．在系統傳輸容量保證的前提下，通過引入D2D中繼協助傳輸，使某些基站可以暫時關閉，達到節約資源的目的．文獻[6]中研究了全雙工模式下D2D中繼通信的自干擾情況．通過提出的最佳功率分配方法，使D2D中繼通信可以在全雙工模式下為系統提供傳輸容量的增益．文獻[7]中聯合研究了D2D通信的中繼選擇、子信道分配和功率分配問題，提出了一種迭代算法以解決網絡吞吐量最大化的問題，獲得了接近最優的結果．文獻[8]通過先確定候選中繼的范圍、后選擇中繼的兩步方法，有效地縮小了D2D通信候選中繼的范圍，降低了中繼選擇的復雜度，且提高了系統的吞吐量．文獻[9]考慮了D2D通信的功率控制和中繼選擇，利用博弈論設計出一種競標的中繼選擇方法．在基站輔助計算下，獲得了系統傳輸容量的最大收益．文獻[10]研究了3種基于物理位置的中繼選擇方式，通過權衡中繼探測代價和系統傳輸容量增益，得到了最佳的基于物理位置的中繼選擇方式．從上述文獻可以看出，當D2D通信引入中繼技術后，整個網絡的性能獲得有效的提升．但是這些研究都將中繼用戶進行理想化的處理，即空閑狀態的設備都能有效地協助轉發數據，并未考慮候選中繼的具體情況．而研究D2D通信中繼選擇的文獻多是只在物理域進行研究，以追求網絡的吞吐量增益為目的．這種從單一維度選擇出的中繼是否能適應真實的場景值得思考．從社會域的角度看，由于社會關系、資源受限、隱私保護等原因，設備并不具有較強的協助轉發數據的意愿[11]．因此，以上研究并未考慮候選中繼設備具體的意愿和能力，在實際場景下極有可能造成用戶體驗降低和通信鏈路質量下降的問題．

基于此，筆者首先從社會網絡中引入威望這一概念，在社會網絡中威望描述了人們尋求幫助時向誰求助的問題．對于小區中的設備，通過設備之間的探測接觸率以及設備剩余能量定義了設備的威望值，同時考慮了物理層信道條件和數據傳輸率的需求．再利用博弈論中一級密封價格報價拍賣方式進行中繼設備的選擇．設計出的這種基于威望的中繼選擇算法(based on Prestige for Relay Selection Algorithm， PRSA)，既保證了網絡的數據傳輸率，又考慮了設備持有者的特性和服務質量．

圖1 單小區網絡構架

1 單小區網絡構架

如圖1所示，考慮單小區場景，其中包含1個基站(Base Station，BS)，N個空閑的候選中繼設備(R1,R2, …,RN)，M個D2D用戶(D1,D2, …,DM)以及K個蜂窩用戶(U1,U2, …,UK)．整個小區中的無線網絡由蜂窩通信和D2D通信構成，移動用戶可以進行傳統蜂窩傳輸、D2D直接傳輸或者D2D中繼傳輸．為了提高頻譜資源的利用率，D2D通信復用蜂窩通信的頻譜資源．

從物理域的角度看，當采用無線資源非正交復用模式時，無論是D2D直接通信還是D2D中繼通信，都會與小區中的某個蜂窩用戶產生同頻干擾．從社會域的角度看，這些集中在一起的用戶彼此之間的社會聯系要強于區域外的用戶．圖1中，若用戶活躍在不同的區域，則彼此之間的接觸較弱；若用戶活躍在相同的區域，則彼此之間的接觸較強．而在集中區域中，那些活躍的用戶幫助傳輸數據的意愿更強，因此這類活躍的用戶更適合被選作中繼．單純考慮物理域，極有可能選擇到通信鏈路質量好但意愿不強的中繼，影響用戶的服務質量，不適用于實際場景．所以，筆者從物理屬性和社會屬性分析通信模型，得到更符合實際場景的中繼選擇方式．

2 中繼選擇算法

受社會網絡中威望概念的啟發，通過設備間的接觸率和設備剩余能量，充分考慮移動設備被選作中繼的意愿和能力．同時，在物理域分析信道質量，保證系統的吞吐量．最后引入博弈論中的一級密封價格報價拍賣機制進行中繼節點的選擇．

2.1 基于設備接觸和剩余能量的威望

網絡中每個移動設備都利用點對點方法感知周圍的情況[12]，且每個設備都有一個探測半徑，設定每個設備的探測半徑是相同的．當兩個設備彼此進入對方的探測半徑時，相互之間能探測到對方，此時接觸開始;當兩個設備彼此離開對方的探測半徑時，此時接觸結束．所以定義設備i和設備j之間的接觸間隔Ti,j為

Ti，j={t-t0:Lt(i，j)≤r，i≠j} ,

(1)

其中，t0表示設備i和設備j上一次接觸結束的時刻;t表示設備i和設備j緊接著的這一次接觸開始的時刻;Lt(i，j)表示在t時刻設備i和設備j之間的物理距離;r表示設備的探測半徑．Lt(i,j)≤r，表示設備i和設備j已經互相進入彼此的探測半徑，開始接觸．

定義用戶i與小區中其他用戶相遇的平均概率: 設小區中有M個用戶，i，j分別是其中任意兩個用戶，且i≠j，則

(2)

(3)

根據文獻[14]提出的無線信道能量模式，且考慮瑞利衰落，則傳輸l位數據且傳輸距離為d的發送能耗為

Et(l,d)=Eelecl+lεampd4,

(4)

其中，Eelec為電路損耗常量，εamp是能耗系數．所以中繼設備在轉發數據后的剩余能量為

(5)

(6)

2.2 物理域分析

以上通過威望從社會域的角度提出了中繼選擇的原則之一．筆者采用無線資源非正交復用方式，D2D鏈路復用蜂窩上行鏈路的頻譜資源，兩種通信方式之間會產生同頻干擾．

圖2 信道模型

如圖2所示，考慮一個蜂窩小區中的基本情況．包括基站BS、蜂窩用戶U1、D2D發送機D1、D2D接收機D2以及中繼設備R，采用經典的3節點中繼通信模式．中繼采用半雙工解碼轉發中繼模式，整個傳輸被分為兩個階段，每一階段有相同的時隙．D2D通信共享蜂窩通信的頻譜資源，為了限制同頻干擾，一條D2D鏈路共享一個蜂窩用戶的資源，一個蜂窩用戶的資源只能被一條D2D鏈路共享．

對于D2D直接通信，D2D接收機在接收D2D發送機的信號時也會受到蜂窩上行用戶的同頻干擾，因此D2D接收到的信噪比為

γD1,D2=PD1hD1,D2/(PU1hU1,D2+σ2) ,

(7)

其中，PD1和PD2分別是D2D發送機和蜂窩用戶的發送功率，σ2是信道中的均值為零的高斯白噪聲，hD1,D2和hU1,D2分別是D2D發送機到D2D接收機的信道增益和蜂窩用戶到D2D接收機的信道增益．信道模型考慮路徑損耗和瑞利衰落．路徑損耗與距離和路徑損耗因子α有關，而每條鏈路都是獨立的瑞利衰落，且期望E[h0]=1，則考慮信道增益hi，j=L-αh0，式中h0是高斯信道系數，是一個常數．因此，根據香農公式，D2D直接通信的傳輸速率為

RD1，D2=Wlb(1+γD1，D2) ,

(8)

其中，W表示信道寬度．

同理，D2D發送機選擇蜂窩模式時，它與基站BS之間的傳輸速率為

Rcell=Wlb(1+PUhD1，BS/σ2) ．

(9)

對于D2D中繼鏈路，通信過程分為兩跳，分別對應T1時隙和T2時隙．第1跳和第2跳的數據傳輸速率為

(10)

(11)

簡單而不失一般性，只要D2D鏈路的傳輸速率能夠不小于蜂窩鏈路的最低值，就可以選擇D2D模式進行數據傳輸，所以

mRcell+(1-m)RD2D≥Rcell,

(12)

其中，m∈(0,1)．當m=1時，表示設備選擇蜂窩模式．

2.3 中繼選擇

以上部分分別從社會域和物理域分析了移動設備的屬性，在本部分中主要分析怎樣選擇出滿足要求的中繼，為此引入博弈論中的一級密封價格報價拍賣機制進行中繼節點的選擇．

對于D2D中繼選擇算法，應該考慮復雜度不能太高的算法．復雜度太高會提高中繼傳輸的時延，影響用戶的服務質量．假設設備在提交收集到的數據時是可靠的．在這種拍賣中，每個報價者都單獨地將報價裝入信封，密封以后交于拍賣者，相互之間不知道報價．拍賣者收集所有報價，從中選擇出報價最高者獲得拍賣物品．獲得物品的贏家需要支付自己所出的報價，而未獲得物品的競拍者不需要任何支付．

根據以上思路，中繼選擇如下：小區移動設備在移動過程中，通過與其他移動設備的歷史相遇情況計算了自己在這個網絡中與其他移動設備的相遇概率．當D2D直接鏈路發現難以達到需求的數據傳輸速率或者鏈路不能建立時，D2D發送機向周圍發送信號通知候選設備進行中繼節點的拍賣．在收到信號需要作為候選中繼進行競標時，周圍設備會探測D2D接收端，計算剩余能量以形成威望;同時計算鏈路的傳輸速率．因此，對于每個中繼候選節點而言，在競標時所出的價格包含兩個方面:威望值和實時中繼傳輸速率．

為了節約設備的資源及降低設備轉發數據的復雜度，設定正在進行數據傳輸的設備不進行中繼的競拍，在接收到競標信號后可以不參與．對于每個中繼候選節點，它的策略集合是

(13)

其中，φ表示空集，即不上傳威望和數據速率信息；β表示設備威望．

D2D發送機作為拍賣者，并不需要關心中繼候選者的數目，且候選中繼數目越多越好，即使在報價的過程中有其他節點進入，也不會影響整個拍賣．因為報價只有一輪，且新加入的節點沒有收到拍賣者發出的拍賣信息[15]，因此新加入的設備不屬于候選設備．

當拍賣者D2D發送機收到候選中繼設備的報價后，會從中選出贏家作為中繼用戶．因為關注的主要問題是鏈路的傳輸速率和中繼設備的威望，因此效用函數構建如下:

(14)

其中，a是單位速率的價值常數．中繼設備的傳輸速率和威望值都是越大越好．等式中大于零，表示D2D中繼方式可達到的數據速率應該比蜂窩通信的數據速率大；否則，不能保證用戶鏈路的質量，也失去了中繼通信的意義．

3 仿真分析

通過仿真對以上算法的性能進行驗證，對比算法包括基于最大吞吐量的中繼選擇算法(based on Maximum Throughput for Relay Selection agorithm，MTRS)；單一D 2D直接通信，即D 2D通信模式下只進行D 2D直接通

表1 主要仿真參數

信；隨機選擇中繼算法(Random Relay Selection algorithm， RRS)．主要仿真參數如表1所示．

如圖3所示，有10對用戶需要通信時，不考慮其他蜂窩用戶的吞吐量．比較了隨著小區中空閑用戶數的增加4種模式下10對用戶的吞吐量，因此可以直觀地看出中繼技術帶來的收益，φmin= 0.3．當選擇進行蜂窩模式通信時，這些用戶就是蜂窩用戶，小區中的空閑用戶的多少不影響其通信．在RRS模式、MTRS模式和PRSA模式下，空閑用戶數的增加意味著中繼通信可能性的增加．對于PRSA模式，當判定D2D通信不能進行時，用戶就選擇蜂窩通信模式．從圖中3可以看出，在相同空閑用戶數下，因為隨機選擇的中繼用戶信道條件可能不滿足通信，系統吞吐量在使用筆者提出的方法下大于RSS方法的，但要小于MTRS模式的．

圖4展示了隨著空閑用戶數的增加，D2D用戶在不同中繼選擇方式下可以進行D2D通信的可能性，即D2D覆蓋率，φmin= 0.3．在小區中有10對用戶可以進行D2D通信，可以選擇3種D2D通信模式(D2D直接通信、RRS和PRSA)．D2D直接通信不需要中繼協助傳輸，所以小區中空閑用戶的數量對其覆蓋率沒有影響．對于筆者提出的模式和隨機選擇中繼模式，當小區中空閑用戶數量增多時，可以作為中繼設備的用戶就增多，進行中繼通信的可能性增大．但是隨機選擇的中繼有可能信道質量差或者設備的剩余能量嚴重不足，就會造成D2D鏈路不能建立; 而筆者提出的模式考慮了這些問題，因此相比較性能更好．例如在空閑用戶為200時，筆者提出的模式比隨機選擇模式覆蓋率高約20%．

圖3 4種模式下吞吐量隨空閑用戶數的變化圖4 3種模式下覆蓋率隨空閑用戶數的變化

在圖5中展示了RRS和PRSA模式下的威望選擇．有10對用戶將進行D2D中繼通信，可以通過RRS和PRSA模式，比較了這10對D2D用戶選擇的中繼的威望之和．從圖中可見，RRS模式下威望增長幅度較小，而PRSA模式下威望增長幅度較大．而且隨著空閑用戶數的增加，兩者的差距變大，這是因為空閑用戶數的增加使候選的中繼設備越多，而筆者提出的模式選擇了其中性能較好的用戶．但是當空閑用戶數較小時，候選中繼設備不充足，筆者提出的方法由于條件的限制有可能不能選擇中繼，因此在這種情況下RRS模式選擇的中繼的威望之和可能大于PRSA模式．所以，筆者提出的PRSA方法在用戶密集的情況下更具有優勢．從社會域的角度，威望越高，說明選擇的設備更有意愿和能力作為中繼，保證了中繼選擇的公平合理．

圖5 兩種模式下威望的比較圖6 吞吐量與剩余能量閾值的關系

圖7 吞吐量與中繼移動速度的關系

在圖6中展示了剩余能量閾值對4種模式下D2D鏈路吞吐量的影響．設定小區中有250個空閑設備，且有10對設備需要通信．在蜂窩模式下，吞吐量不受空閑用戶的影響; 在RRS和MTRS模式下，由于不考慮剩余能量閾值，所以吞吐量也不會受影響．對于筆者提出的PRSA模式，隨著閾值的增加，可選作中繼的設備減少，能進行D2D中繼通信的可能性降低，PRSA的吞吐量會小于RRS，逼近蜂窩模式．

圖7描述了MTRS和PRSA模式下，所選中繼的移動速度對中繼通信系統吞吐量的影響．以250個空閑用戶為例，由圖7可知，隨著中繼的移動速度增加，兩種模式的吞吐量都降低了; 但MTRS模式更嚴重，因為MTRS模式選擇的中繼設備物理位置都較好，中繼的移動對其影響更大．

分析PRSA、MTRS和RRS算法的復雜度．假設有n個空閑用戶可以作為中繼．在PRSA算法下，候選中繼設備記錄了歷史相遇概率和剩余能量并計算出了目前的威望．D2D發送機獲得中繼競標上傳的數據后，將威望值由大到小排序，該步驟復雜度為O(n2)．下一步根據威望值由大到小依次判斷對應中繼的傳輸速率是否滿足條件，其復雜度為O(n)，所以PRSA算法總體復雜度為O(n2)．MTRS算法選擇傳輸速率最大的中繼，其復雜度為O(n)，而RRS算法隨機選擇中繼，所以復雜度為O(1)．

4 結 束 語

筆者首次引入社會網絡中的威望概念，提出一種基于威望的D2D中繼選擇算法．在保證系統容量的前提下，從社會域角度考慮設備被選作中繼的意愿和能力，使中繼的選擇更公平合理．其過程首先通過設備之間的歷史相遇概率和剩余能量確定設備的威望; 然后考慮信道的物理屬性，保證系統的傳輸容量．最后通過一級密封價格報價拍賣方法選擇出適合的中繼．與其他D2D中繼選擇算法相比，筆者考慮了中繼設備的社會屬性，更符合實際的應用．仿真表明，筆者提出的算法能夠在保證中繼設備意愿和能力的前提下，提高系統的性能．

參考文獻：

[1] CISCO. Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, 2016-2021 White Paper[R/OL].[2017-03-10]. https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html.

[2] LIN X, ANDREWS J G, GHOSH A, et al. An Overview of 3GPP Device-to-device Proximity Services[J]. IEEE Communications Magazine, 2014, 52(4): 40-48.

[3] 張銳, 李勇朝, 崔建國, 等. LTE-A網絡下支持終端直通的資源復用選擇策略[J]. 西安電子科技大學學報, 2016, 43(2): 17-22.

ZHANG Rui, LI Yongzhao, CUI Jianguo, et al. Resource Reusing Selection Scheme for Device-to-device Communication Underlaying LTE-A Networks[J]. Journal of Xidian University, 2016, 43(2): 17-22.

[4] ALKURD R, SHUBAIR R M, ABUALHAOL I. Survey on Device-to-device Communications: Challenges and Design Issues[C]//Proceedings of the 2014 IEEE 12th International New Circuits and Systems Conference. Piscataway: IEEE, 2014: 361-364.

[5] LI Y, JIN D P, HUI P, et al. Optimal Base Station Scheduling for Device-to-device Communication Underlaying Cellular Networks[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(1): 27-40.

[6] ZHANG G P, YANG K, LIU P, et al. Power Allocation for Full-duplex Relaying-based D2D Communication Underlaying Cellular Networks[J]. IEEE Transactions on Vehicular Technology, 2015, 64(10): 4911-4916.

[7] KIM T, DONG M. An Iterative Hungarian Method to Joint Relay Selection and Resource Allocation for D2D Communications[J]. IEEE Wireless Communications Letters, 2014, 3(6): 625-628.

[8] ZHAO M, GU X Y, WU D, et al. A Two-stages Relay Selection and Resource Allocation Joint Method for D2D Communication System[C]//Proceedings of the IEEE Wireless Communications and Networking Conference. Piscataway: IEEE, 2016: 7565070.

[9] CHEN Y C, HE S B, HOU F, et al. Optimal User-centric Relay Assisted Device-to-device Communications: an Auction Approach[J]. IET Communications, 2015, 9(3): 386-395.

[10] FENG H, WANG H B, CHU X L, et al. On the Tradeoff between Optimal Relay Selection and Protocol Design in Hybrid D2D Networks[C]//Proceedings of the 2015 IEEE International Conference on Communication Workshop. Piscataway: IEEE, 2015: 705-711.

[11] WU D P, ZHANG H P, WANG H G, et al. Quality of Protection-driven Data Forwarding for Intermittently Connected Wireless Networks[J]. IEEE Wireless Communications, 2015, 22(4): 66-73.

[12] WANG R Y, YANG H P, WANG H G, et al. Social Overlapping Community Aware Neighbor Discovery for D2D Communications[J]. IEEE Wireless Communications, 2016, 23(4): 28-34.

[13] ZHANG B T, LI Y, JIN D P, et al. Social-aware Peer Discovery for D2D Communications Underlaying Cellular Networks[J]. IEEE Transactions on Wireless Communications, 2015, 14(5): 2426-2439.

[14] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[15] MUKHERJEE A, KWON H M. General Auction-theoretic Strategies for Distributed Partner Selection in Cooperative Wireless Networks[J]. IEEE Transactions on Communications, 2010, 58(10): 2903-2915.

RelayselectionalgorithmincorporatedwithprestigeforD2Dcommunication

WANGRuyan1,2，MIAOYi1,2，YANJunjie1,2

(1. School of Telecommunication and Information Chongqing Univ. of Posts and Telecommunications, Chongqing 400065, China; 2. Optical Communication and Network Key Lab. of Chongqing, Chongqing 400065, China)

For the sake of enabling the device-to-device (D2D) communication to impartially and effectively select the relay node, a prestige-based relay selection algorithm is proposed. From a social domain perspective,the prestige is used to describe the will and ability of an equipment to be selected as a relay. Meanwhile the data transmission of the equipment in different transmission modes is analyzed. Finally, a suitable relay is selected amongst the candidate relay equipments by the method of game theory. This algorithm avoids a device with a weak social relation and a low residual energy being selected as a relay. The results manifest that the proposed algorithm improves the throughput of the system, the coverage probability of D2D link, and the rationality of the relay selection, compared with the random selection algorithm and the maximum throughput algorithm.

device-to-device; relays; prestige; throughput

2017-01-15

時間：2017-06-29

國家自然科學基金資助項目(61371097,61271261)；重慶市青年科學人才培養計劃資助項目(CSTC2014KJRC-QNRC40001)；重慶高校創新團隊建設計劃資助項目(CXTDX201601020)

王汝言(1969-)，男，教授，博士，E-mail：wangry@cqupt.edu.cn．

http://kns.cnki.net/kcms/detail/61.1076.TN.20170629.1734.028.html

10.3969/j.issn.1001-2400.2018.01.014

TN925.1

A

1001-2400(2018)01-0076-07

(編輯： 郭 華)