一種基于多跳D2D和社交感知的新穎中繼選擇算法

李良，楊新杰

（寧波大學信息科學與工程學院，浙江 寧波 315211）

0 引言

近年來，隨著移動通信技術以及互聯網行業的迅速發展，智能無線終端得到了快速發展和普及，蜂窩網絡用戶數量呈現爆炸式增長。根據《思科年度互聯網報告（2018—2023年）》，到2023年，全球手機用戶將增加到57億人（占總人口的71%），全球移動設備將增長到131億部[1]。如此龐大的用戶和設備數量，給蜂窩網絡的基站帶來了巨大的負載，同時導致無線頻譜資源短缺、頻譜利用率低下和網絡容量不足等問題日益凸顯[2]。研究人員因此提出了設備到設備（device-to-device，D2D）通信技術以應對上述問題。不同于只允許設備和基站之間通過上行/下行鏈路進行通信的傳統移動通信技術，D2D允許鄰近的移動設備直接進行通信，有效地提高了蜂窩網絡的頻譜效率或吞吐量[3]。另一方面，D2D設備既可以通過使用非授權頻譜或專用蜂窩頻譜實現通信，也可以通過復用蜂窩設備使用的頻譜實現通信[4]。這種復用模式能夠大幅提高頻譜利用率，有助于解決頻譜短缺問題[5]。由于具有多種優勢，D2D技術被3GPP確定為5G關鍵技術之一，受到越來越多研究人員的關注。

傳統的直連D2D具有通信距離短，消耗設備電量多，對蜂窩網絡干擾大等問題。另外，在設備間距離較遠時，直連D2D的源設備可能無法接入目的設備[6]。一些研究人員在 D2D中引入中繼技術，進一步提高了 D2D通信的性能，中繼選擇由此成為D2D中一個重要的研究方向。

為了減少算法執行給基站帶來的負擔，研究人員提出了一些不需要基站參與的中繼選擇算法。文獻[7]提出了一種基于計時器的中繼選擇方法，該方法能夠分布式確定并選擇最好的中繼。文獻[8]提出了一種用以設備為中心的中繼選擇方案。該方案通過交換設備鄰居表獲得D2D通信設備的共同鄰近設備，然后基于信干噪比和剩余電量等多種參數從共同臨近設備中選出最佳的設備作為中繼，相比傳統的以網絡/基站為中心的方案，減少了基站負載和網絡開銷。

另外，為了進一步擴大 D2D通信范圍和提升通信性能，研究人員將研究從單跳延伸到多跳D2D 通信[9]。文獻[10]提出了一種基于 Dijkstra算法的 D2D多跳路由算法，仿真結果表明與單跳直接 D2D通信相比，多跳路徑可以實現更高的吞吐量。文獻[11]提出了一種用于D2D通信的自適應干擾感知多跳路徑選擇算法。該算法通過了解用戶位置，使多跳路徑從 D2D發射端開始首先到達小區邊緣，然后沿小區邊緣移動，最后到達接收端附近時返回小區內部。該算法在小幅度犧牲傳統蜂窩容量的情況下顯著提高了整體網絡容量。

考慮在實際的系統中，設備充當中繼時具有自身意愿問題，研究人員考慮更加現實的場景并將終端的社交域引入D2D研究中。文獻[12]提出了一種利用社交網絡的中繼選擇方法。該方法綜合考慮中繼的物理域和社交域因素，將根據用戶遭遇歷史計算得到的鏈路傳輸穩定性和根據用戶親密度計算得到的合作意愿作為標準選擇中繼。相比傳統的方法，該方法可以提高中繼選擇成功的概率，減輕蜂窩網絡的負擔。文獻[13]提出了一種創新的社交感知節能中繼選擇機制，該機制考慮了移動用戶之間隱藏的社交關系，能夠確保更多用戶愿意參與合作通信。

上述 D2D中繼選擇算法均應用于蜂窩網絡場景，文獻[14]提出了一種應用于物聯網場景的多跳 D2D通信最優路由算法，在算法中融合了社交域信息，通過使用基于排序的信任模型推導得到 D2D連接的信任概率，由信任概率得到了節點間的可信任連接概率，并在算法中考慮了可信任連接概率的影響。最終所提出的路由算法可以使任意一對 D2D以分布式的方式實現最高的可信任連接概率，幾乎達到了通過窮舉搜索實現的性能。

綜上所述，目前在兩跳D2D方面已有一些關于分布式或以設備為中心的中繼選擇算法的研究，但有關多跳D2D中繼選擇的研究基本沒有考慮算法的執行方式和復雜度這一問題。另一方面，現有關于多跳 D2D中繼選擇的研究是基于半雙工中繼，算法的吞吐量性能受到限制。同時，對社交域信息在實際系統中對算法性能的影響的研究還不充分。因此，本文提出了一種用于蜂窩網絡下多跳 D2D通信的中繼選擇算法。通過使用全雙工中繼，保證了多跳 D2D的吞吐量性能。通過合理地設計執行流程，中繼選擇算法在工程實現上能夠以半分布式的方式執行，有效地減少了基站負載。考慮設備充當中繼的意愿問題，在中繼選擇算法中引入了社交域信息，并與沒有引入社交域信息的方案進行了對比。仿真結果表明，相比于對比算法，所提算法在不考慮社交域信息時能夠改善系統的吞吐量和能量效率，在考慮社交域信息時能夠大幅提升系統的能量效率。

1 系統模型

1.1 網絡基礎設施模型

一個單小區蜂窩網絡中的多跳D2D通信物理模型如圖1所示，包括位于小區中心的基站（base station，BS），若干通過上行正交信道與基站通信的蜂窩設備（cellular equipment，CE），若干當前沒有通信需求的空閑設備（idle equipment，IE），多跳D2D通信的源（source，S），多跳D2D通信的目的地（destination，D），以及若干為S和D之間的通信轉發數據的中繼（relay，R）設備。基站配備有全向天線，所有設備配備有兩個天線且工作在全雙工模式。

圖1 多跳D2D通信物理模型

1.2 信道模型

在本文中，假設所有信道均為瑞利衰落信道，同時考慮自由空間傳播路徑損耗，則任意一個節點x向另一個節點y發送信號時節點y的接收信號功率為：

其中，Px表示x的發射功率，表示x和y之間的信道增益，且h~CN(0,1)，表示x0和y之間的距離，α表示路徑損耗指數。

1.3 社交模型

在實際的D2D通信中進行中繼選擇時，由于自身有通信需求或電池電量有限等原因，持有中繼設備的用戶可能不愿意充當他人的中繼，或者不愿意為轉發他人的數據貢獻太多的功率。但是，如果持有中繼設備的用戶和進行D2D通信的用戶有親密的社交關系，那么該用戶就很有可能愿意充當中繼或為轉發D2D通信的數據貢獻更多的功率。因此，在實際的系統中，有必要將社交域信息引入多跳D2D通信的中繼選擇算法中。

在現實生活中，兩個關系密切的人之間一般會通過電話或社交軟件等頻繁地聯系，并且每次聯系時持續的時間比較長；而兩個關系疏遠的人之間一般很少聯系，并且聯系時持續的時間比較短。另一方面，考慮基站可以從數據庫中獲取用戶的通話記錄，并且在用戶通過社交軟件聯系時可以很方便地記錄次數、時長等數據，因此用持有設備的用戶之間通過電話或社交軟件進行聯系的次數和時長來量化他們之間的社交關系，具體的計算式如下：

其中，ui,j表示用戶j與用戶i之間的社交關系強度，Ti,j表示用戶j與用戶i之間的總聯系次數，表示用戶i與所有用戶進行過的聯系的次數之和，Di,j表示用戶j與用戶i之間的總聯系時長，表示用戶i與所有用戶進行過的聯系的時長之和。

根據文獻[15]的研究，絕大多數用戶之間的社交關系強度比較弱，只有少數用戶與其他用戶之間有著較強的社交關系，類似于帕累托分布。帕累托分布的概率密度函數如下：

其中，尺度參數xmin＞0。

在本文中，用帕累托分布建模用戶之間的社交關系強度，并規定中繼的發射功率與他們和源、目的地之間的社交關系強度有關。用uS,j和uD,j分別表示設備j與S和D之間的社交關系強度，則由社交關系強度得到的設備j的發射功率為：

其中，max{?}表示取最大值，Pmax表示中繼的最大發射功率。

2 中繼選擇算法

在某個時刻設備S想要與D進行D2D通信，由于他們之間的距離過遠，因此只能在多個中繼的幫助下才能成功建立D2D通信。在這種情況下需要從源和目的地之間的空閑設備中選出合適的設備作為中繼，幫助轉發S和D之間的數據。但是S和D之間的空閑設備數量眾多，而且不同的空閑設備作為中繼時D2D通信鏈路的性能不同，因此如何選擇中繼成為一個重要的問題。本文提出的中繼選擇算法主要由候選中繼確定方法、被復用頻譜的蜂窩設備確定方法以及中繼選擇算法執行方法3部分組成。

2.1 候選中繼確定方法

毫無疑問，如果將源和目的地之間所有的空閑設備當作候選中繼，并從中選出最佳的中繼可以得到更準確的結果，但這樣會導致算法復雜度過高，不利于實際應用。受多跳認知無線網絡[16]和認知中繼網絡[17]中中繼選擇和路由策略方向相關研究的啟發，同時為了減少算法復雜度，本文提出了一種基于中繼簇（cluster）的候選中繼確定方法，在中繼選擇時只把某些區域中的空閑設備當作候選中繼，然后從中選出最后所需的中繼。

假設S到D之間需要進行M（M≥3）跳D2D通信，則共需要從M-1個中繼簇中選出M-1個空閑設備作為中繼。中繼簇的位置由S和D的位置以及事先設定的距離在S和D之間確定，S和D之間的中繼簇示意圖如圖2所示。每一個中繼簇均為圓心在S和D的連線上、半徑為r的圓形區域。第一個中繼簇的圓心與S之間的距離為r，之后的每一個中繼簇的圓心與前一個中繼簇的圓心之間的距離為L（L＞2r），D與最后一個中繼簇的圓心之間的距離用l表示，0＜l≤L。

圖2 S和D之間的中繼簇示意圖

2.2 被復用頻譜的蜂窩設備確定方法

在本文中，為了提高頻譜利用率，D2D設備通過復用蜂窩設備的頻譜實現通信。為了避免多跳鏈路之間的互干擾以及全雙工帶來的自干擾，D2D通信的每一跳復用不同蜂窩設備的頻譜，即中繼工作在頻分雙工模式。另外，D2D通信復用蜂窩設備的上行頻譜，一方面復用下行頻譜時蜂窩設備接收干擾信號，復用上行頻譜時基站接收干擾信號，而基站處理干擾的能力一般強于蜂窩設備；另一方面，相比于下行頻譜，上行頻譜通常未被充分利用[18]。另外，D2D通信的每一跳復用不同蜂窩設備的頻譜，所以雖然在本文的模型中所有中繼均工作在全雙工模式，但各跳的信道干擾情況可以單獨分析。多跳D2D通信第m跳干擾示意圖如圖3所示，假設Tm和Rm分別為多跳D2D通信第m跳的發射設備和接收設備，Cm為該跳復用的頻譜所對應的蜂窩設備。

圖3 多跳D2D通信第m跳干擾示意圖

為了保證蜂窩設備的正常通信，BS從Cm處接收的信號的信干噪比（）需要達到一定的門限值，即：

其中，PCm表示Cm的發射功率（假設對于所有m，PCm均等于PC），PTm表示Tm的發射功率，，分別表示Cm和BS之間的距離和信道增益，、分別表示Tm和BS之間的距離和信道增益，rth表示BS能正確解碼Cm發送的信號所需要的最小信干噪比（signal to interference plus noise ratio，SINR），N0表示背景高斯白噪聲的功率。由式（5）可以得到：

取：

綜上所述，多跳D2D通信第m跳復用蜂窩設備選擇示意圖如圖4所示，做一直線連接Rm所在中繼簇的圓心和基站并反向延長（在最后一跳Rm即是D，中繼簇的圓心即是D的位置），以延長線上一點為圓心、r/2為半徑做一與保護區域邊界內切的圓，從該圓形區域內的蜂窩設備中選出到基站的接收信號功率最大的蜂窩設備作為第m跳復用的蜂窩設備。合理地設置R的數值既能避免D2D對基站造成嚴重的干擾，又能減小，增加，由式（8）可知第m跳的將增加，即該跳的吞吐量將增加。綜上所述，根據上述過程選取的蜂窩設備可以改善D2D鏈路的吞吐量性能，同時又能保證蜂窩設備的QoS。

圖4 多跳D2D通信第m跳復用蜂窩設備選擇示意圖

2.3 中繼選擇算法執行方法

多跳D2D通信在每一跳中既要從多個蜂窩設備中選出被復用頻譜的設備，又要從中繼簇中的多個空閑設備中選出中繼，涉及的設備數量過多，如果完全由基站以集中式完成中繼選擇過程，必然會給基站帶來過量負載和大量信令開銷。本文提出的中繼選擇算法能夠以半集中式的方式執行，基站只需完成D2D多跳通信開始時的信道參數、節點位置等信息的收集及少量的數據處理，中繼選擇則由參與多跳D2D通信的設備自行完成。

假設S和D之間的D2D通信總共M跳，則需要復用M個蜂窩設備的頻譜，用F={f1,f2,…,fM}表示第一跳到第M跳復用的頻譜。另外需要M-1個中繼設備，這M-1個中繼設備從M-1個中繼簇中選出，從簇 1到簇M-1確定的中繼分別用R1,R2,…,RM?1表示，每個中繼簇中有N個空閑設備作為候選中繼。用Pn′,m表示由式（4）得到的第m個中繼簇中第n個空閑設備在考慮社交關系的情況下的發射功率，用P′ ={P1′,1,… ,Pn′,m,… ,PN′,M?1}表示各中繼簇內的空閑設備在考慮社交關系情況下的發射功率集。用Pn′′,m表示由式（7）得到的第m個中繼簇中第n個空閑設備在考慮干擾的情況下的最大發射功率。

忽略設備發現過程，具體的中繼選擇過程如下。

步驟1S、D發送D2D多跳通信請求到BS。

步驟2BS首先確定S、D的位置，然后根據第2.1節的方法確定各中繼簇的位置、范圍、其中包含的空閑設備和各空閑設備的位置，并通知各中繼簇中的空閑設備其已被選作對應簇中的候選中繼。接著根據數據庫內的通話記錄計算所有空閑設備與S和D的社交關系并得到集合P'，根據D及各簇的位置由第2.2節的方法確定各跳復用頻譜對應的蜂窩設備共M個，記錄這些蜂窩設備的頻譜F。最后，BS記錄S、各簇中的空閑設備與BS之間的信道增益，連同S、D和各簇中空閑設備的位置以及集合P'、F發送給D。

步驟3D將從BS處接收的數據發送給簇M-1中的空閑設備并將自己信號接收頻率設為fm。

步驟4簇M-1中的各空閑設備根據式（7）計算在考慮干擾的情況下其發射功率最大值然 后 取{P1,M?1,… ,PN,M?1}=min{{·},{·}}表示取集合對應元素最小值。假設簇M-1中的各空閑設備在從D處收到數據的同時可以獲得他們與 D之間的信道增益，則根據{P1,M?1,… ,PN,M?1}、簇M-1中的各空閑設備到D的信道增益由式（1）可得到他們發送信號給D時D的接收信號功率。然后各個空閑設備開啟一個終止時間與其到D的接收信號功率成反比的計時器，接收信號功率最大的空閑設備的計時器最先結束，該設備即RM?1。然后RM?1向簇M-1中的其他空閑設備廣播一條自己已被選作中繼的消息，簇M-1中的其他空閑設備遂停止計數并得知自己未被選中。最后RM?1將從D處接收到的數據發送給簇M-2中的空閑設備，并將自己的信號發送頻率設為fM，信號接收頻率設為fM?1。

步驟 5各簇中的空閑設備重復步驟 4中的處理過程直至S根據式（7）確定其發射功率，并將其信號發送頻率設為f1。

步驟6S開始D2D通信。

可以看出，根據上述步驟確定多跳通信鏈路后，每一跳的 SINR也即確定，故可用香農公式計算每一跳的吞吐量。假設蜂窩設備頻譜帶寬用B表示，則第一跳的吞吐量為：

中間第m跳的吞吐量為：

最后一跳的吞吐量為：

由于所有中繼設備均工作在全雙工模式，因此整條多跳D2D通信鏈路的吞吐量由吞吐量最小的那一跳的吞吐量決定，即多跳D2D通信的吞吐量為：

3 仿真結果及分析

本節給出所提出的算法通過仿真得到的數值結果，并與對比算法進行比較。仿真模擬了一個半徑為 500 m、以配備全方向天線的基站為中心的圓形單小區蜂窩場景，蜂窩設備和空閑設備在小區內隨機均勻分布。詳細的仿真參數及其取值見表1。仿真中的社交感知（social awareness，SA）和非社交感知（social unawareness，SUA）算法為本文所提算法，SA算法中空閑設備的發射功率既考慮對蜂窩設備的干擾、同時也考慮社交關系，SUA算法中空閑設備的發射功率只考慮對蜂窩設備的干擾，不考慮社交關系；MLS0（max link selection，最大鏈路選擇）、HTPRS0（highest transmit power relay selection，最大發射功率中繼選擇）為對比算法，由于認知無線網絡中的一些多跳中繼選擇算法所考慮的系統模型與本文的系統模型類似，因此MLS和HTPRS均選自認知無線網絡相關文獻。

表1 仿真參數及其取值

不同S和D間距離下算法吞吐量比較如圖5所示，可以看出所有算法的吞吐量均隨著距離的增加而減少，這是因為隨著距離的增加，所增加的跳只會導致各跳吞吐量的最小值不變或減少，所以整條鏈路的吞吐量會相應減少。在距離相等的情況下 SUA算法的吞吐量高于 MLS和HTPRS，這是因為SUA算法選擇中繼的指標與每一跳的 SINR直接相關，能夠選出性能更好的中繼。而在距離相等的情況下 SA算法的吞吐量不如SUA，這是因為SA算法對所有空閑設備的發射功率施加了額外的社交關系約束，所以 SA算法選出的中繼的發射功率必定小于SUA算法選出的中繼。

圖5 不同S和D間距離下算法吞吐量比較

不同中繼簇中空閑設備數量下算法吞吐量比較如圖6所示。結果表明，SUA、SA和MLS 3種算法的吞吐量均隨著空閑設備數量的增加而增加，這是因為隨著空閑設備數量的增加，這3種算法能有更大的概率選出性能更好的空閑設備作為中繼，而HTPRS算法選擇中繼時隨機性更大，無法利用更多的空閑設備這一優勢。在空閑設備數量相同的情況下 SUA算法的吞吐量大于MLS和 HTPRS的吞吐量，而 SA算法的吞吐量不如SUA算法的吞吐量。

圖6 不同中繼簇中空閑設備數量下算法吞吐量比較

不同S和D間距離下算法能量效率比較如圖7所示，能量效率定義為鏈路吞吐量與所有參與多跳D2D通信的設備的實際發射功率之和的比。結果表明所有算法的能量效率均隨著距離的增加而減少，這是因為隨著距離的增加參與D2D通信的中繼數量也在增加，這導致發射功率之和隨之增加，而所有算法的吞吐量隨著距離的增加而減小，因此能量效率減小。在距離相等的情況下SUA算法的能量效率優于MLS和HTPRS，而SA算法的能量效率遠遠超過其他3種算法。這是由于SA算法通過對所有空閑設備施加額外的社交關系約束，減少了每一跳被選出的中繼的發射功率，因此發射功率之和大幅減少，雖然SA算法比SUA的吞吐量要低，它的能量效率卻遠遠超過了另外3種算法。

圖7 不同S和D間距離下算法能量效率比較

不同中繼簇中空閑設備數量下算法能量效率比較如圖8所示。結果表明SUA、SA和MLS 3種算法的能量效率均隨空閑設備數量的增加而增加，HTPRS的能量效率均隨空閑設備數量的增加基本保持不變。在空閑設備數量相同的情況下SUA的能量效率優于MLS和HTPRS，而SA算法的能量效率遠遠超過其他3種算法。

圖8 不同中繼簇中空閑設備數量下算法能量效率比較

SA和SUA算法性能比較見表2，總結了SA和SUA兩種算法在不同S和D之間距離下的性能比較。可以看出，SA和SUA兩種算法在吞吐量和能量效率兩方面的性能差異很大，且在能量效率方面 SA相比于 SUA有很大優勢，因此在D2D中繼選擇算法的研究中不能忽略社交域信息的作用。

表2 SA和SUA算法性能比較

4 結束語

本文提出了一種用于單小區蜂窩網絡下多跳D2D通信的中繼選擇算法。首先在算法中引入了持有設備的用戶之間的社交關系，以解決設備充當中繼時的意愿問題，并使算法更具有現實意義；其次為了提高多跳D2D鏈路的吞吐量，不同于以往假設中繼是半雙工設備的研究，本文的模型基于全雙工中繼；然后為了避免全雙工帶來的嚴重的干擾，令中繼工作在頻分雙工模式；最后通過合理設計，算法能夠在較少依賴基站的情況下運行，有利于實際工程實現。蒙特卡洛仿真驗證了所提算法的性能。仿真結果表明所提算法在不考慮社交關系信息時吞吐量和能量效率均優于對比算法，在考慮社交關系信息時吞吐量會小幅下降，但能量效率會大幅提高。這使本文所提算法在電池技術沒有突破性進展和倡導節能減排的今天具有一定的實際應用價值。