基于社會域和物理域的自適應(yīng)D2D多播分簇算法

汪漢新 ，任星倩

(中南民族大學(xué) 電子信息工程學(xué)院&智能無線通信湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430074)

近年來，隨著物聯(lián)網(wǎng)技術(shù)和無線通信的發(fā)展，導(dǎo)致了智能終端數(shù)量和移動通信量的快速增加[1]，同時人們對通信時延和系統(tǒng)容量的要求越來越高[2].D2D通信作為第五代移動通信網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，通過復(fù)用蜂窩用戶的頻譜資源，不需要基站和中心網(wǎng)絡(luò)的轉(zhuǎn)發(fā)，實(shí)現(xiàn)相鄰用戶之間的點(diǎn)到點(diǎn)直接通信，能夠降低基站負(fù)載，提高系統(tǒng)頻譜利用效率[3-5].然而隨著移動終端用戶的增多，面臨著在同一場景下多個終端對相同數(shù)據(jù)內(nèi)容進(jìn)行請求的問題[6]，如果使用相鄰用戶之間一對一的單播通信進(jìn)行傳輸容易造成數(shù)據(jù)的重復(fù)發(fā)送，而且終端的負(fù)載也相對較大.相比于單播通信，多播通信通過簇頭用戶以多播方式發(fā)送給簇內(nèi)成員用戶，無需基站重復(fù)發(fā)送給每一個用戶，可以進(jìn)一步的提高系統(tǒng)吞吐量和頻譜的的利用率[7-8].D2D多播通信在進(jìn)行數(shù)據(jù)傳輸前需對D2D用戶進(jìn)行劃分，找出簇頭用戶和簇成員用戶，合理有效的分簇策略是高效資源分配的前提保證.如何進(jìn)行合理的簇頭和簇成員劃分將會直接影響到相鄰D2D用戶是否能穩(wěn)定有效的進(jìn)行內(nèi)容共享[9].同時，由于D2D多播通信的分簇是基于群體用戶，用戶之間的可信任度，安全性以及用戶意愿等都將直接影響到通信鏈路的穩(wěn)定性和可靠性[10-11]，因此在進(jìn)行D2D多播分簇時，不僅需要考慮物理域中用戶之間的位置關(guān)系，還需要結(jié)合社會域中用戶之間的社會關(guān)系.另外，D2D多播通信用戶的接入率也是D2D多播通信急需解決的問題[12]，因?yàn)閷τ诿芗嗖ネㄐ诺膱鼍?，形成多播簇的用戶越多，基站的?shù)據(jù)重復(fù)發(fā)送量就越少，所以在對D2D多播分簇算法進(jìn)行設(shè)計(jì)時，還應(yīng)該考慮如何提高用戶的接入率.

目前，現(xiàn)有的D2D多播用戶分簇的方法主要有k-medoids算法、博弈論、貪婪迭代算法等.文獻(xiàn)[13]提出一種改進(jìn)k-medoids的基于用戶信道質(zhì)量的多播分簇算法，以最大化多播簇容量為目標(biāo)，通過密度聚類算法選取簇頭，再通過k-medoids算法分簇，該算法只考慮了單一的距離因素，忽視了社會因素對分簇結(jié)果的影響，并且未對用戶接入率進(jìn)行分析.文獻(xiàn)[14]以最大多播組能量效率為目標(biāo)，提出了利用信息聯(lián)盟博弈方法去解決簇形成的過程，分簇過程分為簇頭選擇和簇形成兩個算法求解目標(biāo)問題，雖然考慮了社會因素對分簇結(jié)果的影響，但是該算法的復(fù)雜度較高，可能會增加資源分配過程的時延，并且D2D多播用戶的接入率不高.文獻(xiàn)[15]利用貪婪迭代算法對D2D多播用戶進(jìn)行分簇，通過選取親密度最高的用戶作為簇頭，并將與其相連的所有用戶直接劃分到該簇中，以此迭代得到分簇結(jié)果，該算法雖然考慮了社會因素，并對用戶接入率進(jìn)行了分析，但是在簇成員的選取上存在一定的缺陷，即在劃分簇成員時，未考慮簇成員自身的親密度值，忽視了高親密度值用戶作為簇成員會導(dǎo)致部分用戶無法接入的問題，從而降低了D2D多播用戶的接入率.

本文針對D2D多播分簇算法中存在的接入率不高的問題，提出了一種基于社會域和物理域的自適應(yīng)D2D多播分簇算法(SD-AMC).首先利用分段函數(shù)自適應(yīng)產(chǎn)生一個簇成員親密度閾值，然后根據(jù)用戶親密度值的大小找出第一個簇頭，通過此簇成員親密度閾值對第一個簇頭的簇成員進(jìn)行選取，完成該簇的劃分后，再尋找下一個簇頭；每找出一個簇頭后，簇成員親密度閾值減1，用于下一個簇頭的簇成員選取，直到當(dāng)簇成員親密度閾值等于1后，不再減少；當(dāng)剩余用戶中最大親密度值為1時，則停止簇頭的尋找；最后對簇內(nèi)成員數(shù)進(jìn)行檢查,如果存在空簇，則以物理距離最優(yōu)原則，將空簇的簇頭作為簇成員加入與其相連的簇中，得到分簇結(jié)果.提出的SD-AMC算法，可以在不同可復(fù)用信道數(shù)量和信道狀態(tài)信息的情況下，實(shí)現(xiàn)對簇成員親密度閾值的自適應(yīng)調(diào)節(jié)，使最終的分簇?cái)?shù)量與信道數(shù)量盡量匹配，進(jìn)而提高D2D多播用戶的接入率.

1 基于社會域和物理域的D2D多播網(wǎng)絡(luò)模型

圖1為考慮社會域和物理域的D2D多播通信場景示意圖.其中，小區(qū)中有一個基站BS、15個用戶U1-U15，每個用戶對應(yīng)一個節(jié)點(diǎn)，雙實(shí)線表示兩個用戶之間只滿足社會域通信條件，單虛線表示兩個用戶之間只滿足物理域通信條件，單實(shí)線表示兩個用戶之間同時滿足社會域和物理域通信條件.根據(jù)用戶對需求內(nèi)容的不同，將用戶劃分成不同的社區(qū)，圖中給出了2個社區(qū)，其中7個黑色用戶和8個白色用戶分別構(gòu)成2個不同的社區(qū).根據(jù)用戶所在社區(qū)和用戶之間滿足的通信條件來劃分多播簇，圖中共劃分成了3個D2D多播簇{y1,y2,y3}.

(a)D2D多播用戶接入率的仿真結(jié)果 (b)簇內(nèi)平均成員數(shù)的仿真結(jié)果 (c)形成簇?cái)?shù)的仿真結(jié)果 圖1 基于社會域和物理域的D2D多播通信場景Fig.1 D2D multicast communication scenarios based on socialand physical domain

假設(shè)系統(tǒng)中用戶總數(shù)為N，用戶之間形成x個社區(qū)S={s|s1,s2,…,sx}，每個社區(qū)內(nèi)的用戶請求相同的數(shù)據(jù)內(nèi)容，不同社區(qū)之間請求的數(shù)據(jù)內(nèi)容不同.在社區(qū)sx中有Mx個活躍用戶，用集合mx來表示，其中mx={mxa|a=1,2，…，Mx}.同時滿足社會和物理域通信條件的用戶組成K個D2D多播簇，多播簇的集合表示為Y={y|y1,y2,…,yk}.

2 基于社會域和物理域的自適應(yīng)D2D多播分簇算法

為了降低部分高親密度的用戶成為簇成員的可能性，我們將當(dāng)前親密度值最大的用戶作為簇頭后，通過設(shè)置一個簇成員親密度閾值將親密度值低于該閾值的用戶劃分入簇，排除掉高親密度用戶，使其參與下一個簇頭的選取.對于找到的第k個簇頭，我們把簇成員親密度閾值用符號ωk來表示，ωk取值為0～N之間的整數(shù).提出的基于社會域和物理域的自適應(yīng)D2D多播分簇算法SD-AMC的步驟如下：

(1)對小區(qū)內(nèi)的用戶進(jìn)行統(tǒng)計(jì)，把請求相同內(nèi)容的用戶劃分到同一個社區(qū)，得到社區(qū)的集合S；

(3)根據(jù)可復(fù)用信道數(shù)量和信道狀態(tài)信息條件以分段函數(shù)的方式自適應(yīng)的產(chǎn)生第一個簇頭的簇成員親密度閾值ω1，并令k=1；

(5)對剩余用戶再次進(jìn)行親密度值的統(tǒng)計(jì)，并令k=k+1，重復(fù)步驟(4)，直到當(dāng)剩余用戶中最大親密度值為1時，則停止簇頭的尋找；

(6)查找剩余用戶是否與已找出的簇頭相連，如果只與一個簇頭相連，則直接加入到與其相連的簇頭所在簇中，如果與多個簇頭相連，則以物理距離最近原則加入到相應(yīng)簇中；

(7)檢查所有多播簇是否存在空簇，如果存在，則刪除該簇，將該簇頭作為剩余用戶按照步驟(6)的原則將其加入到相應(yīng)簇中，最終得到分簇集合Y.

由于上述多播分簇算法是通過簇成員親密度閾值ωk對簇成員進(jìn)行篩選，從而達(dá)到控制分簇結(jié)果的目的，而每完成一次簇成員篩選后，ωk+1=ωk-1，因此需要選取合適的第一個簇頭的簇成員親密度閾值ω1來控制分簇結(jié)果.同時，在現(xiàn)實(shí)的密集多播通信場景中，信道數(shù)量和信道質(zhì)量具有時變性，所以在SD-AMC分簇算法中，通過根據(jù)不同信道數(shù)量和信道質(zhì)量來自適應(yīng)選取ω1，使最終的分簇?cái)?shù)量與可復(fù)用信道的數(shù)量盡量匹配，提高多播用戶的接入率.

用物理距離閾值D_th表示在物理域中用戶之間進(jìn)行通信的最大距離值，社會關(guān)系閾值S_th表示在社會域中用戶之間進(jìn)行通信的最小社會關(guān)系，對ω1取固定值進(jìn)行了實(shí)驗(yàn)，發(fā)現(xiàn)當(dāng)D_th越大，接入率越高，形成的簇?cái)?shù)先增多再減少；當(dāng)S_th越小，接入率越高，形成的簇?cái)?shù)先增多再減少.當(dāng)ω1=1時，所形成的簇?cái)?shù)為最大，此時的用戶接入率最高；隨著ω1增大，形成的簇?cái)?shù)依次減少，用戶接入率也依次降低；當(dāng)ω1增加到一定值時，簇?cái)?shù)不再隨著ω1的增大而減少，此時可看作對簇成員的篩選不加條件控制.如果考慮一個多播簇只能復(fù)用一個信道資源的場景，在可復(fù)用信道數(shù)量有限的條件下，可能會出現(xiàn)形成的簇?cái)?shù)大于可復(fù)用信道數(shù)的情況，這時ω1=1顯然不適用，因此應(yīng)該根據(jù)信道的數(shù)量自適應(yīng)的選取ω1值，使形成的簇?cái)?shù)與可復(fù)用信道數(shù)量盡量匹配.在ω1取固定值時，簇?cái)?shù)的變化可以分為上升和下降2個階段，在上升段，簇?cái)?shù)隨著D_th的增大而增大，當(dāng)簇?cái)?shù)達(dá)到最大值后開始進(jìn)入下降段，即簇?cái)?shù)隨著D_th的增大而減少.因此，我們提出SD-AMC算法，采取自適應(yīng)調(diào)整ω1值的方式來最大化上升段和下降段所形成的簇?cái)?shù)，使最終的分簇?cái)?shù)量與可復(fù)用信道的數(shù)量相匹配，從而提高多播用戶的接入率.

用SD_th表示社會域和物理域共同影響用戶之間進(jìn)行通信因素，其表達(dá)式為：

(1)

當(dāng)D_th越大或S_th越小，則SD_th的值越大.為了使最終的分簇?cái)?shù)量與可復(fù)用信道數(shù)量相匹配，在自適應(yīng)選取ω1值時，將ω1取值隨著SD_th的變化分為上升的初始段和控制段以及下降段：

a1),

(2)

(3)

在分段函數(shù)的上升控制段和下降段，當(dāng)可復(fù)用信道數(shù)足夠大時，此時ω1取值可能會出現(xiàn)為負(fù)值的情況，若在計(jì)算過程中出現(xiàn)ω1≤0，則取ω1=1.

綜上所述，ω1的取值可以表示為以下分段函數(shù)，并將其作為SD-AMC算法中ω1值的自適應(yīng)選取函數(shù).

(4)

3 仿真結(jié)果與復(fù)雜度分析

本文在MATLAB仿真平臺對SD-AMC算法進(jìn)行仿真實(shí)驗(yàn)，設(shè)置社區(qū)數(shù)S=2，系統(tǒng)用戶數(shù)量N=500，且用戶隨機(jī)分布在小區(qū)內(nèi)，用戶之間的社會關(guān)系值為0～10之間的隨機(jī)數(shù)，具體實(shí)驗(yàn)參數(shù)如表1所示.

表1 實(shí)驗(yàn)參數(shù)Tab.1 Experimental parameters

我們對ω1選取固定值和自適應(yīng)選取ω1值分別進(jìn)行了仿真實(shí)驗(yàn)，具體的仿真結(jié)果如下：

(1)ω1為固定值的仿真.

圖2是在不同D_th和S_th下，簇成員親密度閾值ω1分別選取不同固定值時，對D2D用戶接入率，簇內(nèi)平均成員數(shù)以及形成簇?cái)?shù)與貪婪迭代算法(Greedy)進(jìn)行對比仿真實(shí)驗(yàn).圖中ω1=1，ω1=20，ω1=40,ω1=60,ω1=80分別表示ω1選取1，20，40，60，80時的仿真結(jié)果.從圖2(a)可以看出D_th越大，D2D用戶的接入率越高，S_th越小，D2D用戶接入率越高.這是因?yàn)镈_th越大和S_th越小代表越多的用戶能夠滿足物理域和社會域通信條件，從而加入多播簇.從圖2(a)還可以看出采取設(shè)置簇成員親密度閾值的方法比貪婪迭代算法能顯著提高D2D多播用戶的接入率，且ω1取值的越小，用戶接入率越高，當(dāng)ω1=1時，D2D多播用戶的接入率最高，這是因?yàn)棣?值越小，代表篩選簇成員時的條件越嚴(yán)格，但是從圖2(b)和圖2(c)可以看出ω1值越小，形成的簇?cái)?shù)就越多，簇內(nèi)平均成員數(shù)也越少，可能會導(dǎo)致分簇?cái)?shù)量與可復(fù)用信道的數(shù)量不匹配，因此我們需要對ω1值進(jìn)行自適應(yīng)調(diào)整.

(a)D2D多播用戶接入率的仿真結(jié)果 (b)簇內(nèi)平均成員數(shù)的仿真結(jié)果 (c)形成簇?cái)?shù)的仿真結(jié)果圖2 固定ω1值時D2D多播用戶接入率，簇內(nèi)平均成員數(shù)以及形成簇?cái)?shù)的仿真結(jié)果Fig.2 Simulation results of D2D multicast user access rate, average members number of a cluster and number of formed clusters for fixed ω1

(2)自適應(yīng)選取ω1值的仿真.

圖3是將ω1=30和ω1=80時形成的最大簇?cái)?shù)值分別作為可復(fù)用信道數(shù)，采用提出的SD-AMC算法在不同D_th和S_th條件下，對D2D多播用戶接入率和形成簇?cái)?shù)與固定的ω1值時的對比仿真實(shí)驗(yàn)結(jié)果.圖中SD-AMC1，SD-AMC2分別表示選取可復(fù)用信道數(shù)為ω1=30和ω1=80形成的最大簇?cái)?shù)值時使用SD-AMC算法的仿真結(jié)果.從圖3(a)可以看出，隨著D_th的增大，采用SD-AMC算法所形成的簇?cái)?shù)基本穩(wěn)定在可復(fù)用信道數(shù)附近，而固定ω1值時所形成的簇?cái)?shù)在達(dá)到可復(fù)用信道數(shù)值后就開始下降，說明SD-AMC算法形成的簇?cái)?shù)能夠更好的與可復(fù)用信道數(shù)相匹配.同時從圖3(b)可以還看出SD-AMC算法的D2D多播用戶接入率總體高于固定ω1值時接入率.

(a)形成簇?cái)?shù)的仿真結(jié)果 (b)D2D多播用戶接入率的仿真結(jié)果圖3 SD-AMC算法與固定ω1值的D2D多播用戶接入率和形成簇?cái)?shù)對比仿真結(jié)果Fig.3 Smulation results of formed clusters number and D2D multicast user access rate for SD-AMC algorithm compared with fixed ω1

為了驗(yàn)證SD-AMC算法中ω1值的自適應(yīng)選取函數(shù)的有效性，我們在不同D_th和S_th以及可復(fù)用信道數(shù)分別為180，160，140，120，100，80的條件下，對SD-AMC算法的D2D多播用戶接入率和形成簇?cái)?shù)與貪婪迭代算法和ω1=1進(jìn)行了對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4，其中，SD-AMC1，SD-AMC2，SD-AMC3，SD-AMC4，SD-AMC5，SD-AMC6分別對應(yīng)可復(fù)用信道數(shù)為180，160，140，120，100，80的仿真結(jié)果.從圖4(a)可以看出SD-AMC1和SD-AMC2形成的簇?cái)?shù)與ω1=1時形成的簇?cái)?shù)基本重合，這是因?yàn)镾D-AMC1和SD-AMC2所能形成的最大簇?cái)?shù)小于當(dāng)前的可復(fù)用信道數(shù)，此時分段函數(shù)中ω1取值接近為1；同時可以看出SD-AMC6和貪婪迭代算法形成的簇?cái)?shù)基本重合，這是因?yàn)镾D-AMC6所能形成的最小簇?cái)?shù)大于當(dāng)前的可復(fù)用信道數(shù)，此時分段函數(shù)中ω1取值足夠大，可看作對簇成員的篩選不加親密度閾值的控制，即等同于貪婪迭代算法；我們還可以看出SD-AMC3，SD-AMC4，SD-AMC5能夠使形成的簇?cái)?shù)維持在當(dāng)前可復(fù)用信道數(shù)附近.從圖4(b)可以看出SD-AMC算法所形成的最小簇?cái)?shù)大于當(dāng)前可復(fù)用信道數(shù)時，接入率與Greedy算法相當(dāng)；而當(dāng)前可復(fù)用信道數(shù)介于SD-AMC算法所形成的最小簇?cái)?shù)和最大簇?cái)?shù)之間時，SD-AMC算法的接入率均高于Greedy算法，并且可復(fù)用的信道數(shù)越多，提升的接入率越大；當(dāng)SD-AMC所形成的最大簇?cái)?shù)不超過可復(fù)用的信道數(shù)時，SD-AMC算法的D2D多播用戶接入率比貪婪迭代算法可以提高約10%.

(a)形成簇?cái)?shù)的仿真結(jié)果 (b)D2D多播用戶接入率的仿真結(jié)果圖4 在不同可復(fù)用信道數(shù)條件下SD-AMC算法的D2D多播用戶接入率和形成簇?cái)?shù)與Greedy算法和ω1=1的對比仿真結(jié)果Fig.4 D2D multicast user access rate and formed clusters number of SD-AMC compared with Greedy and ω1=1 under different multiplexable channel numbers

(3)復(fù)雜度分析.

提出的SD-AMC算法在進(jìn)行多播分簇時，首先對所有用戶進(jìn)行親密度統(tǒng)計(jì)，并根據(jù)用戶親密度值大小進(jìn)行簇頭和簇成員劃分，在劃分好一個簇以后對剩余用戶重新進(jìn)行親密度值統(tǒng)計(jì)，并找出下一個簇頭和簇成員，因此算法的復(fù)雜度與系統(tǒng)用戶數(shù)目有關(guān)，并且形成的簇?cái)?shù)也會影響用戶親密度值的統(tǒng)計(jì)和找尋簇頭的次數(shù).假設(shè)系統(tǒng)用戶數(shù)目為N，形成的簇?cái)?shù)為K，則計(jì)算用戶親密度值的復(fù)雜度為O(N2)，通過親密度值尋找簇頭和簇成員的復(fù)雜度為O(N2)，因此經(jīng)過K次迭代形成K個簇?cái)?shù)的復(fù)雜度為O(K*N4)，而SD-AMC算法采取分段函數(shù)對第一個簇頭的簇成員親密度閾值進(jìn)行選取是在進(jìn)入迭代找簇頭和簇成員之前進(jìn)行，對整個算法復(fù)雜度的影響可以忽略不計(jì)，因此SD-AMC算法的總體復(fù)雜度為O(K*N4)，與貪婪迭代算法的復(fù)雜度相當(dāng).

4 結(jié)語

為了適應(yīng)不同信道條件的通信場景，提高D2D多播用戶的接入率，本文提出了一種基于社會域和物理域的D2D多播自適應(yīng)分簇算法.首先設(shè)置簇成員親密度閾值對簇成員進(jìn)行劃分，然后對找到的第一個簇的簇成員親密度閾值取固定值進(jìn)行了分析，提出采取分段函數(shù)對簇成員親密度閾值進(jìn)行自適應(yīng)選取，使最終的分簇?cái)?shù)量與信道數(shù)量盡量匹配，進(jìn)而提高多播用戶的接入率.提出的SD-AMC算法能針對可復(fù)用信道數(shù)量不斷變化的通信場景，實(shí)現(xiàn)對簇成員親密度閾值的自適應(yīng)調(diào)節(jié)，并有效提升D2D用戶接入率.