基于簇內能耗最優的設備到設備緩存通信內容共享算法

佟 飄，龍 隆，韓 雪，邱大偉，胡 茜

(1.重慶郵電大學寬帶無線移動互聯網絡實驗室，重慶400065;2.移動計算與新型終端北京市重點實驗室(中國科學院計算技術研究所)，北京100190))

(* 通信作者電子郵箱tongpiao@ict.ac.cn)

0 引言

近年來，由于智能設備終端數量快速增長，產生了多種新的無線服務，導致無線網絡的移動數據流量急劇增長，給蜂窩網通信帶來了巨大的壓力。根據思科的預測［1］，在未來十年，全球移動數據流量預計有500倍的增長，其中移動視頻流量占移動數據總流量的50%。

目前，以蜂窩網為基礎的設備到設備(Device to Device，D2D)緩存通信作為一種將流量從蜂窩網基站卸載的方案已經引起了學術界和工業界極大的興趣［2］。事實上，隨著智能終端設備的本地存儲容量增加且硬件存儲成本的降低，可以充分利用用戶終端設備進行文件存儲。在D2D網絡中各個用戶節點設備處緩存流行文件并進行終端設備之間文件共享能夠有效地卸載蜂窩網基站流量，緩解蜂窩網通信容量瓶頸問題［3］。但終端設備電池容量有限，不能滿足用戶持久性的D2D內容共享，如何降低數據傳輸能耗、提高文件卸載率是一個亟待解決的問題。

文獻［3－6］提出以用戶為中心的主動緩存策略，通過優化緩存分布來提升D2D緩存通信的卸載率，但其方案都沒有充分考慮到文件的獲取來源、傳輸過程中節點的能量消耗問題以及能耗對卸載率的影響。文獻［7］中報告表明，在實際生活場景中，用戶的行為在時間段內具備規律性，活動區域相對固定且與鄰近的用戶交互較多。從目前的研究來看，基于分簇的通信方案能夠有效地提高卸載率。文獻［8］采用分簇的方案，通過優化傳輸距離提高蜂窩網流量卸載，然而該算法并未對節點能耗的問題進行研究，忽略了設備的續航時間對文件卸載的影響。文獻［9］基于信道質量和傳輸能耗，提出了一種成簇方案，該算法可有效提高系統吞吐量增益，然而以最大功率進行文件傳輸的策略造成了傳輸過程中的設備能耗過大，并沒有對能耗對卸載率的影響進行研究。

在本文的研究中，考慮D2D用戶的場景，提出基于簇內節點能耗最優的緩存通信內容共享算法(Caching communication content Sharing Algorithm for minimizing inner-Cluster node energy consumption，CCSA)。其基本思路是，在全網用戶節點生成D2D簇的基礎上，根據簇首(Cluster Head，CH)影響因子對每個D2D簇進行CH選取，在此基礎上將D2D網絡的卸載率歸納為一個組合優化問題［10］。通過選取最優的CH集，促使CH能夠滿足其所在簇的絕大多數成員(Cluster Member)的內容需求;同時分析傳輸距離與文件卸載能耗的制約關系，優化傳輸距離;在能耗最優的條件下，實現D2D緩存通信卸載率的最大增益，并最大限度地延長系統的生存周期。

1 系統模型

考慮如圖1所示的D2D用戶場景中，將全網用戶節點建模為泊松簇過程(Poisson Cluster Process，PCP)［9］。同簇的設備除了可以進行正常蜂窩網上下通信外，還能在D2D鏈路上進行設備間直接通信;D2D通信在蜂窩基站控制下進行，為了降低干擾，D2D和蜂窩通信使用正交時頻資源。由于簇內各設備間距較短，如同一單位、企業、校園，D2D鏈路的傳輸速率較高，一個普通視頻文件的傳輸可達秒級完成(如一部500 MB電影)。網絡中的每一個節點都具備有限的本地數據緩存的能力，不能夠緩存文件庫中所有文件;可以作為內容提供者為其他用戶提供服務;節點的自身的能量有限，一旦低于一定能量值就不能進行文件共享。DR表示內容請求節點，DT表示內容提供節點;DT與DR通過建立D2D鏈路進行文件共享。如果DT節點分布過疏，會導致通信半徑rc過大，傳輸能耗過多;且當DT能量低于一定閾值，則不足以支撐文件傳送。以上這些因素都會影響系統生存周期，導致D2D緩存通信的卸載量下降。

現實生活場景中，用戶設備的緩存容量、能量有限，在不同時間段用戶位置、請求的文件具有動態變化性，因此本文引入了D2D簇的機制和“輪”的概念。假設在短時間范圍內用戶的位置基本不變，網絡中各D2D簇在每輪時間都會進行CH更新，在持續的一段時間段內(如5小時)用戶的位置可能會發生移動、興趣偏好及請求的文件的流行度可能會發生變化，因此一輪持續的時間即D2D簇的CH更迭頻度與用戶的移動性、設備現存能量、文件的流行度及長度有關，T={t|d，E，β，F}。

圖1 D2D緩存通信網絡Fig.1 D2D cache communication network

基站負責對小區中所有節點進行分簇及簇節點的管理與維護，當節點位置發生變化時需要告知基站;D2D節點需要周期性地向基站上傳自身數據;簇成員需要維護與每輪所在簇的CH節點的通信;CH節點負責維護與本簇所有節點的通信。CH節點的位置疏密度、自身能量很大程度上決定了D2D網絡的卸載率及生存周期，因此，CH節點的選取非常重要。每輪時間開始即簇形成的初始階段，基站根據CH選取算法決定簇中節點是否作為本簇“CH”，并在各個簇內進行泛洪廣播。在簇的穩定階段，當成員節點與CH之間無文件請求服務時(處于空閑狀態)，將成員節點與CH轉換為休眠模式以降低自身能耗;當成員節點發起文件請求服務、CH收到源于簇內成員節點的文件請求時，從休眠狀態轉為工作狀態并重新連接通信鏈路，本文假設節點的狀態轉換不消耗能量。CH負責為簇內多數成員節點提供文件服務。在D2D簇通信網絡中，通過以“輪”為周期動態CH的選取，避免了CH節點能耗過大，防止低能量節點成為CH，最大限度地均衡網絡能耗負載。CH選取算法不僅降低了D2D緩存通信中的能量消耗，且提高了D2D通信網絡的可靠性。

本文考慮蜂窩網下單個小區的場景，用戶節點的地理位置服從密度為λ的泊松簇過程［9］，如圖2所示。假設網絡中包含簇的數量為K，C={C1，C2，…，CK};每個簇的節點數為N，簇中節點以中心節點為中心，獨立同分布，且服從方差為的正態分布，Node={node1，node2，…，nodeN}。小區中每個簇具有相同屬性，且基站明確每個簇所有用戶的地理位置坐標及緩存的文件的種類與數目，并協調D2D通信。

假設小區中的所有用戶可能請求的文件都包含在一個靜態的內容目錄中，數目為Nf。文件在文件庫中的排名索引值源于文件在網絡中的流行度，每個文件的大小為F MB。排名為f(f=1，2，…，Nf)的文件被用戶請求的概率 p(f)服從Zipf［11］分布:

當DR與DT在同一個簇，距離d小于D2D通信距離閾值rc，且兩者的現存能量大于能量閾值，則能夠成功建立D2D數據傳輸鏈路。如果DR在簇內不能通過D2D鏈路獲得請求內容，則向基站請求。

圖2 D2D成簇模型網絡拓撲Fig.2 D2D clustering model network topology

2 自適應加權CH選取算法

2.1 CH選取及更新機制的提出

在D2D用戶成簇的場景中，采用一種組合加權算法以及貪婪算法局部最優原則對每個簇進行自適應CH選取，以達到優化D2D緩存網絡內容共享能耗的目的。自適應加權的原則是給每一個節點分配一個加權和(wCHi(k))，它指示節點適合充當本簇CH的程度。貪婪算法解釋在某種意義上的局部最優解［12］。每輪時間初始，首先借助節點之間的距離、能量制約因素，確定不同制約因子對優化目標即節點的CH權值wCH，k={k∈C|k≤K}的貢獻。其次在滿足節點能量閾值Eh條件下，采用局部最優貪婪機制選擇最大的鏈路和能量組合，即 max(珔d，Ecurrrent/E0)。CH 選擇完成之后，為了滿足內容共享連續性約束，D2D網絡生存周期以“輪”為單位，動態地更新所有簇的可接入CH集合。

在一輪時間內，如果系統中無滿足能量閾值的節點，即CH集合為空，算法結束;否則進行下一輪時間的CH選擇。上述最差情況出現在所有節點的能量都小于閾值，則不能進行D2D緩存通信文件卸載。

在D2D簇初始階段，將網絡中每個簇的位置中心節點作為簇的CH，即第一輪D2D用戶節點簇的CH，為成員節點提供文件服務。對于簇的穩定階段，根據本文提出的基于節點距離和現存能量的CH選取策略，用于第一輪之后的時間段內的動態CH選擇，目的是降低文件傳送的能耗成本，延長每個簇的生存周期，從而提高系統D2D緩存通信的卸載率。在第一輪內容共享結束后，所有簇的CH由CH選取算法確定。

一旦DT與DR建立D2D鏈路，DR處的信號與干擾加噪聲比(Signal to Interference plus Noise Ratio，SINR)［13］可表示為:

其中:Pt表示DT的傳送功率;σ02表示高斯白噪聲的方差;h和r分別表示信道系數以及DT和DR之間的距離，h服從單位方差內的零均值高斯分布;α表示路徑損耗指數。

根據文獻［12］，1+γ(r)約服從γ分布，對于小尺度信道衰落的平均數據傳輸速率［13］可以推導為:

其中W表示帶寬。

通過使用一階近似［14］，文件大小為F的平均傳輸時間可以表示為F/珔R。

2.2 預測節點的現存能量

假設一輪時間內每個簇存在節點個數Nx向其所在簇的CH請求文件，則通過距離為r的D2D鏈路的內容共享能耗為:

其中CH的能耗［10］為:

簇內成員節點的能耗為:

式中:Pr(r)和Pt(r)分別表示DT的傳送功率和DR的接收功率;Pc表示節點自身的功耗;η表示功放效率。

假設簇中的每個節點在系統初始階段所具備的能量都是E0，且節點從休眠轉換為工作狀態不消耗能量，經過一輪時間t后，各個節點經過傳送或接收文件、自身能耗，現存能量為Ecurrent。

每個節點當前時間(第ring_c輪)現存能量模型為:

其中:ring_c≥1;k表示D2D網絡中簇的編號。

2.3 節點之間的距離

假設D2D節點R與S之間的距離為d:

其中，R與S在小區中的坐標為NodeR=(xR，yR)，NodeS=(xS，yS)。

根據歐氏定理，有:

那么，簇內節點i(i=1，2，…，N)到其他節點的平均距離為:

2.4 自適應加權CH選取

針對D2D網絡中的每個簇，考慮簇中節點位置的疏密度以及其現存能量，確定是否作為本簇的CH。簇中節點位置越疏，即DT與DR之間的平均距離越大，節點的傳輸能耗越多，自身能量越低，進而導致文件卸載量降低;反之，節點現存能量越高，系統生存周期越長，進行文件卸載的概率則越大。可能出現一種極端情形，位置越疏的節點，其現存能量越高。針對以上情景，在CH選擇過程中，通過引入δ、θ作為節點的現存能量比率、地理位置疏密度的權重因子，可動態調整，某個參數對目標優化問題越重要，對應權重因子越大，并滿足δ+θ=1的制約條件，具體取值根據應用環境決定。

第ring輪(ring ＞ 1)，計算簇k(k=1，2，…，K)包含的節點i的CH權值wCHi(k)，在約束條件下，從備選CH節點中選擇CH權值最優的節點:

其中δ+θ=1，0≤δ≤1，0≤θ≤1。

根據式(12)，設定兩個對應的閾值 dh、Eh，若 Ecurrent，i＜Eh，則能量權重因子δ取值為0;若di＞dh，則距離權重因子θ取值為0。最優的CH權重值為:

通過式(12)自適應得到網絡中每個簇各個節點的當選權重，根據貪婪局部最優原則選擇權值最大的節點作為本簇當前輪的CH，并通過基站在簇中進行廣播。

3 基于D2D簇的內容共享算法

為了減輕蜂窩網基站負載，本文力求找出每個簇最優的CH，并通過優化通信距離最大化卸載率。在每一輪時間開始，選取當前簇的CH，并為其所在簇的成員節點提供當前輪內容服務。

蜂窩網包含簇的個數為K，用戶節點在一輪持續時間段(0，t)時間內，可請求一個文件至多一次，多個用戶節點可同時訪問同一個文件，則同時訪問文件排名為f、用戶數為n的概率為:

請求文件f的節點在它所在的簇k的通信范圍rc內獲得緩存文件的概率［7］為:

針對文件庫中的所有文件，根據式(14)、(15)可獲得當前簇k的卸載率:

其中0≤n≤N。

由式(16)可推導出系統中K個簇的卸載率:

則由式(18)平均每個簇的卸載率:

于是可將優化卸載率問題建模［15］如下:

函數是關于WCH(k)、n、Nf的凸函數，n和Nf是目標函數的線性約束，根據KKT條件［14］，可求得CH權重因子的最優解WCH*(k)。具體算法流程如下:

1)根據歐氏定理，計算簇中節點i與其余節點之間的平均距離 珔di，并獲取節點的當前剩余能量 Ecurrent，i(i=1，2，…，N)。

2)由式(12)，在每輪生存周期的開始階段根據距離制約因子珔di和節點的現存能量Ecurrent，i求解當前輪所有簇包含的節點i的CH權重值wCHi(k)，為網絡中CH集的選取作準備工作。

3)基于以上步驟，判斷D2D簇的各節點的現存能量是否大于能量閾值，若大于則運行步驟4);否則，網絡中所有簇的CH集合為空，算法結束。

4)在節點的現存能量滿足能量閾值Eh的條件下求解式(13)，即得到簇k最優的CH權重值WCH*(k)，從而獲取當前輪網絡中所有簇的最優CH節點的集合，即:

4 實驗與結果分析

實驗的硬件環境為聯想 G470AH-ITH(i)，Intel酷睿i3-2350M處理器，主頻為2.3 GHz。利用Matlab 2014a仿真平臺對成簇隨機選CH(Random)算法算法及文獻［15］中非成簇能耗優化(Energy Cost optimal，EC)算法進行仿真性能比較。Random算法在D2D用戶成簇場景中采取隨機選取CH策略，每輪時間初始階段基站在每個簇當前所有D2D用戶節點中隨機選取節點作為其所在簇的CH，為其成員節點提供內容服務。

根據系統模型，對于單小區蜂窩網絡，其范圍設為500 m×500 m，用戶節點在小區中隨機分布，并進行泊松成簇，密度 λ =0.03，方差 σnode=10。

文件庫中目錄長度Nf=1 000，其中每個文件大小F=30 MB，Zipf分布的參數β=1，信道的傳輸帶寬W=20 MHz，σ02=－95 dBm，路徑損耗α=4。節點的最大傳輸功率Pmax=23 dBm，功放η=0.2，節點設備自身電量消耗Pc=115.9 mW。CH選取算法中現存能量比率權重因子和位置疏密度權重因子 δ、θ分別取 0.6、0.4。

為了反映DT傳送一個文件所消耗的電量，本文將能耗比率［15］定義為:

其中:Q表示電池容量，單位是mAh;V0表示運行電壓。

用戶設備的運行電壓 V0=4 V，電池容量 Q =1800 mAh(目前手機普遍的電池容量，如iPhone6s)。

為了驗證本文提出的CCSA的性能優勢，將該算法與Random算法以及EC算法進行比較。在仿真實驗對比中，選取D2D緩存通信的通信距離、生存周期(以輪為單位)、現存能量比率、卸載率四個性能指標。其中:現存能量比率定義為當前時間網絡中所有節點的現存能量與初始能量的比值;卸載率定義為針對文件庫中所有文件平均每個簇的卸載率。

圖3(a)顯示了在系統運行一定時間內，CCSA、Random、EC算法在傳輸距離rc變化時系統卸載率的變化趨勢。伴隨rc在一定范圍內的增大，DT能夠滿足更多DR節點數對文件的請求，因此三種算法的卸載率均呈現遞增趨勢，同時得益于CCSA算法考慮每個簇的CH節點相對于成員節點之間的位置疏密、節點現存能量的動態變化，可以觀察到其卸載率性能伴隨著rc的增大而逐漸凸顯，相比Random及EC算法可以更加有效地提高D2D用戶文件的卸載率。

網絡的現存能量比率反映了節點在滿足文件需求的同時自身能量的消耗情況。如圖3(b)中所示，rc較小時，即CH的通信范圍較短，簇中多數成員節點通過訪問基站獲取文件，其能耗遠大于D2D緩存通信的能耗，所以系統的現存能量比率較低;隨著rc的增大，簇中成員節點通過D2D緩存通信的方式獲取文件所占的比重，逐漸大于通過訪問基站獲取文件所占的比重，所以三種算法的系統現存能量比率隨著rc的增大而增大。由于EC算法在系統中隨機選取DT進行文件卸載，因此在文件卸載時受限于傳輸距離和節點能量，網絡的現存能量比率低于CCSA和Random算法。由圖3(b)可見，在rc=80 m時，CCSA和Random算法的現存能耗比率相差最大，約達到40個百分點。

圖3 D2D通信距離與不同性能指標之間的仿真關系Fig.3 Simulation relationship between D2D communication distance and different performance indicators

圖4 (a)為了系統生存周期與D2D緩存通信卸載率的變化情況。顯然，系統生存周期越長，D2D緩存通信的卸載率越高。圖中CCSA、Random、EC三種算法的卸載率均隨著生存周期的增加而增大，當系統運行到一定周期，CCSA算法的卸載率趨于峰值并持平。由圖4(a)可知，當ring=2000時，與Random和EC算法相比，CCSA卸載性能最好，卸載率分別提升約4.6個百分點、5.5個百分點。

圖4(b)為CCSA、Random、EC三種算法的系統生存周期與現存能量的關系。隨著生存周期的延長，三種算法的系統現存能量比率呈現下降趨勢，當生存周期達到一定長度，三種算法的現存能量比率差異逐漸消失。相比Random、EC算法，采用CCSA的系統生存周期較長，CH權值最優促使簇的能耗均衡負載，當ring=500時，現存能量比率高出約56個百分點，能耗較低，且CCSA的系統生存周期分別延長了約60個百分點、72個百分點。

綜上所述，在D2D緩存通信網絡中通過對簇內節點考慮位置、現存能量因素自適應選取 CH，相比隨機選取 CH(Random)算法、非成簇能耗優化(EC)算法，在一定通信范圍內，能夠實現卸載率的提升，并降低了D2D簇節點的能耗，延長了系統生存周期。

圖4 系統的生存周期與不同性能指標之間的仿真關系Fig.4 Simulation relationship between survival cycle of system and different performance indicators

5 結語

針對D2D緩存網絡中用戶設備電量有限的實際情況，本文提出了以最大化D2D網絡卸載率為目標進行節點能耗優化的內容共享算法。在D2D網絡節點成簇的基礎上，設計簇內基于貪婪機制的自適應CH的動態選取方案，并對D2D緩存通信的卸載率和節點能耗進行建模與分析，在兼顧D2D緩存通信系統卸載率的同時，有效地控制了網絡中各簇D2D節點的文件卸載能耗，使內容共享能耗最低。仿真結果表明，相對于Random算法及EC算法，本文提出的CCSA算法通過簇內最優CH的選取，在系統卸載率和生存周期具有明顯的優勢。但該研究并未涉及選取CH的更迭替換時間，即“輪”的持續時間，因此下一步研究計劃以一種自學習機制從用戶的移動性、興趣偏好、文件流行度及長度等方面對系統中簇內CH的更迭頻度進行優化。