林輝

（渭南師范學(xué)院計(jì)算機(jī)學(xué)院，陜西渭南 714000）

近年來，無線蜂窩網(wǎng)絡(luò)（WCN）中的通信量一直在迅速增長。應(yīng)當(dāng)注意，在WCN 中經(jīng)常發(fā)生許多用戶同時(shí)請(qǐng)求相同數(shù)據(jù)的情況[1-2]，例如最新的信息分發(fā)服務(wù)（例如新聞，股票市場(chǎng)等）和文件分發(fā)（例如軟件更新）。多播流量占總流量的百分比較大。在WCN 的傳統(tǒng)可靠多播方案中，基站（BS）重復(fù)發(fā)送相同的數(shù)據(jù)包，直到所有接收者都接收到為止，從而導(dǎo)致大量的多播通信負(fù)載[3-4]。因此，開發(fā)高效的WCN多播方案非常重要，該方案能夠有效減少BS 的數(shù)據(jù)重傳，同時(shí)保證所需的性能水平（如包傳送率、吞吐量等）[5-10]。

到目前為止，在設(shè)計(jì)WCN 有效的多播方案方面已經(jīng)完成了許多工作[11-16]。例如，Low 等人提出了優(yōu)化的機(jī)會(huì)多播調(diào)度（OMS），通過使用最大數(shù)據(jù)速率在每個(gè)時(shí)隙中僅向用戶的“最佳”部分傳輸數(shù)據(jù)，來確保多用戶分集和多播增益之間的權(quán)衡，從而確保用戶成功解碼。與傳統(tǒng)的單播和廣播調(diào)度相比，OMS 大大減少了向所有用戶發(fā)送有限長度消息所需的總傳輸時(shí)間[3]。與OMS 不同，Araniti 等人旨在同時(shí)利用多個(gè)資源塊（RB）來為每個(gè)時(shí)隙中的所有多播用戶提供服務(wù)，以實(shí)現(xiàn)更高的吞吐量，并提出了一種自適應(yīng)RB 分配策略，該策略將多播組劃分為子組并優(yōu)化分配的RB 數(shù)[4]。

1 系統(tǒng)模型

系統(tǒng)模型設(shè)計(jì)的重點(diǎn)是從蜂窩網(wǎng)絡(luò)的一個(gè)小區(qū)中的BS 向彼此接近的N個(gè)用戶設(shè)備可靠地組播公共數(shù)據(jù)，從而形成D2D-MC（多播簇）?？紤]準(zhǔn)靜態(tài)衰落信道，其中隨機(jī)信道增益在多播一個(gè)數(shù)據(jù)包的持續(xù)時(shí)間內(nèi)保持恒定。

假設(shè)BS 在開始傳送一個(gè)新數(shù)據(jù)包時(shí)就了解所有D2D 鏈路的瞬時(shí)信道功率增益。文中提出基于D2D 通信的重發(fā)方式，其中所有重發(fā)器都基于TDMA 模式使用單個(gè)信道而不是多個(gè)信道。這種重發(fā)方式具有小區(qū)內(nèi)每個(gè)D2D-MC 僅占用一個(gè)信道的良好特性，這點(diǎn)很重要，因?yàn)閃CN 中可用的通道總數(shù)非常有限。具體如下：BS 首先向D2D-MC 中的所有設(shè)備發(fā)送（物理層廣播）分組，并且從正確地接收到數(shù)據(jù)的每個(gè)設(shè)備向BS 發(fā)送一個(gè)ACK 分組。然后，根據(jù)所有D2D 鏈路的當(dāng)前信道功率增益，BS 精心地將每個(gè)NACK 設(shè)備與某個(gè)附近的ACK 設(shè)備（不一定是最近的設(shè)備）相關(guān)聯(lián)。將一個(gè)ACK 設(shè)備及其關(guān)聯(lián)的NACK 設(shè)備的組合稱為一個(gè)子集群。最終，具有至少一個(gè)關(guān)聯(lián)NACK 設(shè)備的ACK 設(shè)備（稱為重發(fā)器），在TDMA 模式下使用相同的信道將數(shù)據(jù)重傳到其各自關(guān)聯(lián)的NACK 設(shè)備。重發(fā)器以該子群集中具有最低D2D 信道功率增益設(shè)備確定的最低速率進(jìn)行傳輸，以確?？梢韵蛟撟尤杭械乃蠳ACK 設(shè)備提供多播服務(wù)。

2 問題描述

定義了一組二進(jìn)制變量bi,j，如果bi,j=1，則第j個(gè)NACK 設(shè)備與第i個(gè)ACK 設(shè)備相關(guān)聯(lián)，否則bi,j=0，其中i∈I和j∈J。顯然，由于每個(gè)NACK 設(shè)備必須與一個(gè)且只有一個(gè)ACK 設(shè)備相關(guān)聯(lián)，因此應(yīng)滿足以下約束:

此外，令gi,j表示從第i個(gè)ACK 設(shè)備到第j個(gè)NACK 設(shè)備D2D 鏈路的信道功率增益。對(duì)于第i個(gè)子集群，令gi表示其最差的D2D 鏈路的信道功率增益，即：

在式（2）中，如果第j個(gè)NACK 設(shè)備不與第i個(gè)ACK 設(shè)備相關(guān)聯(lián)（即bi,j=0），則，也就是說，gi實(shí)際上獨(dú)立于第j個(gè)NACK 設(shè)備；如果第j個(gè)NACK 設(shè)備與第i個(gè)ACK 設(shè)備相關(guān)聯(lián)（bi,j），則第i個(gè)ACK 設(shè)備（第i個(gè)子集群）的傳輸速率可以表示為：

其中，B是信道帶寬，pi是第i個(gè)ACK 設(shè)備的傳輸功率，σ2是噪聲功率。

因此，第i個(gè)ACK 設(shè)備的傳輸時(shí)間為：

其中，L是數(shù)據(jù)包的大?。ㄒ詁it為單位）。

由于重發(fā)器以TDMA 模式訪問無線介質(zhì)，因此每個(gè)數(shù)據(jù)包傳遞的所有重發(fā)器的總消耗時(shí)間（TTC）為：

因此，對(duì)TTC 的約束表示為：

此外，ACK 設(shè)備（i即第i個(gè)子集群的重發(fā)器）的能耗為：

每個(gè)數(shù)據(jù)包中所有重發(fā)器的總能耗為：

應(yīng)該注意的是，對(duì)于僅具有ACK 設(shè)備且沒有任何關(guān)聯(lián)的NACK 設(shè)備的特殊子集群，即第i個(gè)子集群，對(duì)于任何j∈J，根據(jù)式（2）gi,j/bi,j=∞，從 而gi=∞。根據(jù)式（3）、式（4）和式（7），對(duì)于這種特殊的子集群，Ri=∞，Ti=0 和Ei=0。因此，總時(shí)間消耗T和總EC與沒有關(guān)聯(lián)的NACK 設(shè)備的ACK 設(shè)備（子集群）無關(guān)。

基于以上分析，可以將考慮的優(yōu)化問題表述為:

顯然，問題P1 是混合整數(shù)規(guī)劃問題（MINLP）。一般來說，MINLP 問題很難解決，因此效率不高存在多項(xiàng)式時(shí)間解。將其分為兩個(gè)子問題，并按順序解決：選擇一個(gè)好的AP 問題以及為給定AP 優(yōu)化重發(fā)器的傳輸功率。在此，可以由向量準(zhǔn)確表示NACK 設(shè)備的AP，其滿足式（1），不同的向量代表不同AP。

3 MINLP問題的有效算法

如上所述，將MINLP 問題P1 分解為兩個(gè)子問題。文中對(duì)于前一個(gè)子問題，提出一種啟發(fā)式算法來找到一個(gè)好的AP。對(duì)于后面的子問題，將其轉(zhuǎn)換為一個(gè)凸問題，并提出了一種用于獲得最佳傳輸功率的最優(yōu)算法。

3.1 采用啟發(fā)式算法選擇好的NACK設(shè)備的AP

當(dāng)ACK 設(shè)備的子集與NACK 設(shè)備相關(guān)聯(lián)并給定時(shí)（即候選重發(fā)器的集合），找到良好的NACK 設(shè)備的AP。在此，將與NACK 設(shè)備相關(guān)聯(lián)的ACK 設(shè)備的子集稱為候選重發(fā)器模式（CRP）。然后，進(jìn)一步介紹一種選擇較好的候選重發(fā)器模式的方法。

當(dāng)給定候選重發(fā)器模式時(shí)，用啟發(fā)式算法關(guān)聯(lián)NACK 設(shè)備。此過程包括兩個(gè)階段：初始化階段和迭代改進(jìn)階段。用I′表示給定CRP 的ACK 設(shè)備的索引集，顯然，I′∈I。

初始化階段包括以下3 個(gè)階段。第一階段：對(duì)于每個(gè)NACK 設(shè)備j，將其關(guān)聯(lián)到擁有最大信道功率增益gi,j{gi.j,i∈I′} 的最佳ACK 設(shè)備i中；第二階段：對(duì)于任 何ACK 設(shè)備i∈I′，如果沒有關(guān)聯(lián)的NACK 設(shè)備，則從I′中刪除i；第三階段：對(duì)于任何ACK 設(shè)備i∈I′，找到最差的NACK 設(shè)備（具有最小的D2D 信道功率增益），并將其關(guān)聯(lián)到ACK 設(shè)備中，表示為，并通過記錄索引，即：

在迭代改進(jìn)階段，每一輪NACK 設(shè)備關(guān)聯(lián)改善如下。對(duì)于每個(gè)，i∈I′，檢查是否存在一個(gè)ACK設(shè)備l滿足以下條件：一旦NACK 設(shè)備與ACK設(shè)備l相關(guān)聯(lián)，在與ACK 設(shè)備l相關(guān)的設(shè)備中，如果找到了這樣的ACK 設(shè)備l，則從ACK 設(shè)備i切換到ACK 設(shè)備l，即：和顯然，移除的從第i個(gè)子集群到第l個(gè)子集群，不會(huì)降低第l個(gè)子集群的多播速率，但增強(qiáng)了第i個(gè)子集群的多播速率。切換后，以前最差A(yù)CK 設(shè)備i的NACK 設(shè)備已切換，更新的值。一旦完成了上述對(duì)的檢查和切換操作，對(duì)于任何ACK 設(shè)備i∈I′，都沒有相關(guān)的NACK 設(shè)備，請(qǐng)從I′中刪除i。如果在這輪NACK 設(shè)備關(guān)聯(lián)中改進(jìn)，不進(jìn)行任何關(guān)聯(lián)卸載，迭代改善階段結(jié)束。另外需注意，給定CRP 中的某些ACK 設(shè)備最終可能不是重發(fā)器。選擇好的CRP 算法：為了要找到好的CRP，一種簡單的方法是設(shè)計(jì)一個(gè)有效的迭代式、啟發(fā)式算法，通過以下方式獲得相應(yīng)AP 的CRP，然后運(yùn)行上述算法。但是，考慮到一臺(tái)D2D-MC 內(nèi)的接收器數(shù)量通常不能太高（例如N=20），并且BS 有很強(qiáng)的計(jì)算能力，檢查每個(gè)CRP 的性能以找到最佳選擇可能。例如，在N=20 并且NACK=10 這種情況下，只有-1=1 023 個(gè)CRP 需要檢查。此外，仿真結(jié)果（在下一節(jié)中顯示）證明即使在拓?fù)浣Y(jié)構(gòu)中N大（例如30）時(shí)，最佳CRP 通常僅包括少數(shù)重發(fā)器。因此，文中算法是檢查重發(fā)器編號(hào)小于預(yù)設(shè)值Lth（例如9）的每個(gè)CRP，以找出良好的（通常是最佳的）CRP。設(shè)置適當(dāng)?shù)腖th值取決于ACK 設(shè)備NACK 的 數(shù)量。NACK 越大，Lth的適當(dāng)值越大?？梢灶A(yù)先從仿真結(jié)果中獲得針對(duì)不同NACK 的Lth的適當(dāng)值，然后將其應(yīng)用于在線操作。至于評(píng)估一個(gè)CRP 的性能指標(biāo)及其相應(yīng)的AP，需應(yīng)用指標(biāo)越小，（CRP，AP）匹配對(duì)才更好。值得注意的是，在方案中，CRP及其對(duì)應(yīng)AP 的選擇與傳輸功率無關(guān)。下一節(jié)中介紹一個(gè)可以共同使用的算法在，以獲得一對(duì)（CRP，AP）的最佳傳輸功率，因此根據(jù)式（8）可知其EC。傳輸功率顯示，指標(biāo)EC 比指標(biāo)更能準(zhǔn)確評(píng)估一對(duì)（CRP，AP）的性能。但是，這種聯(lián)合選擇AP和重發(fā)功率具有更高的計(jì)算能力，其性能只是略勝于文中方法。這種輕微的增長很有可能是[0%，0.5%]，其取決于拓?fù)洹?/p>

3.2 給定AP的功率優(yōu)化算法

文中提出了在給定的AP 條件下優(yōu)化傳輸功率的子問題。根據(jù)問題P1 的描述，該子問題P2 的公式為：

為了揭示該子問題的實(shí)質(zhì)，首先給出以下引理。

引理1：能量消耗Ei嚴(yán)格單調(diào)，隨傳輸功率pi的增加而增加。由于篇幅，此處證明省略。設(shè)P=p1,p2,…,pNACK代表問題P2 的解決方案。顯然，問題P2不是凸優(yōu)化問題，因?yàn)槠淠繕?biāo)函數(shù)不是凸函數(shù)。因此，要獲得最佳解決方案并不容易。接下來，通過將優(yōu)化變量pi替換為變量ti，將其轉(zhuǎn)換為凸優(yōu)化問題。

根據(jù)式（4）可知：

因此，將式（17）代入P2 的目標(biāo)函數(shù)有：

在證明該問題是凸的之前，先給出以下引理，可以更深入地進(jìn)行理解。

設(shè)a=

拉格朗日對(duì)偶問題為：

眾所周知，Karush-Kuhn-Tucker（KKT）原始條件既必要又充分，具有零對(duì)偶間隙的對(duì)偶最優(yōu)變量：

其中，u-1(x) 為u(x) 的反函數(shù)。從可以求出λi，由式（26）和式（17）可以求出ti和pi。

4 實(shí)驗(yàn)結(jié)果

4.1 通過使用D2D通訊來降低BS的多播流量

對(duì)于傳統(tǒng)的多播方案，表1 顯示了在不同的蜂窩鏈路條件下每個(gè)數(shù)據(jù)包的平均傳輸次數(shù)（以nˉ表示）。在這里蜂窩鏈路狀況的特征在于數(shù)據(jù)包傳輸率（PDR）的范圍[pmin,pmax]，每個(gè)接收者的PDR 為在此范圍內(nèi)的隨機(jī)值。需注意，在D2D 通訊中基于BS的方案，BS 僅發(fā)送給每個(gè)分組一次。

從表1 可以看到，N=10 時(shí)，并且每個(gè)PDR 接收器大于0.8，n等于1.8，因此BS 的多播流量負(fù)載減少了44.4%以上。隨著接收者數(shù)量的增加或PDR的減少，多播流量負(fù)載進(jìn)一步減少。例如，當(dāng)N=20 且[pmin,pmax]為[0.6，1.0]時(shí)，BS 使用D2D 通信的組播流量負(fù)載低于傳統(tǒng)組播方案的三分之一。

表1 使用D2D實(shí)現(xiàn)的BS處的組播業(yè)務(wù)負(fù)載減少通訊

4.2 對(duì)重發(fā)器能源消耗的評(píng)估

由于D2D-MC 的可用D2D 重傳方案目的不是優(yōu)化重發(fā)器的EC，并在重發(fā)器中使用固定的傳輸功率。將提出的基于D2D 通信的重發(fā)方案與兩種沒有使用重發(fā)器編號(hào)自適應(yīng)方案進(jìn)行了比較，在第一種方案中，重發(fā)器的數(shù)量固定為一個(gè)。對(duì)于每個(gè)候選重發(fā)器（即每個(gè)ACK 設(shè)備），使用文中算法確定其最佳傳輸功率。然后，最終選擇具有最低EC 的ACK 設(shè)備作為重發(fā)器。在第二種方案（稱為兩次重發(fā)器方案）中，重發(fā)器的數(shù)量固定為兩個(gè)。與第一種方案類似，使用窮舉法，選擇具有最低EC 的兩個(gè)ACK 設(shè)備作為重發(fā)器。在仿真中，所有設(shè)備都隨機(jī)分布在半徑為30 m 的磁盤中。結(jié)果在隨機(jī)生成的拓?fù)浣Y(jié)構(gòu)上是平均的。使用g表示的路徑損耗模型計(jì)算每個(gè)D2D 鏈路的信道功率增益，當(dāng)d=10 m時(shí)，該損耗為-50 dB。圖1 表示出了在不同η下每個(gè)分組的平均EC。首先，可以看出每個(gè)方案隨著η的增加，能量消耗減少。這是因?yàn)殡S著η的增加，不僅NACK增加，以便可以選擇更好的AP，而且NNACK也減少。其次，對(duì)于每個(gè)η，兩個(gè)重發(fā)器方案的性能優(yōu)于單重發(fā)器方案，并且文中方案大大優(yōu)于兩個(gè)重發(fā)器方案。例如，當(dāng)η=4∶6 時(shí)，兩個(gè)重發(fā)器與一個(gè)重發(fā)器方案相比，該方案將EC 降低了21.21%，與兩次重發(fā)方案相比，文中方案進(jìn)一步將EC 降低了40.77%。具體來說，一個(gè)重發(fā)器方案僅使用一個(gè)重發(fā)器服務(wù)于所有NACK設(shè)備，因此通常是集群的信道功率增益非常小，導(dǎo)致在允許的持續(xù)時(shí)間為Tth內(nèi)傳送L位，需要非常大的發(fā)射功率。兩個(gè)重發(fā)器方案，與一個(gè)重發(fā)器方案相比，每個(gè)子簇的gi大得多，因此Ei小得多。

圖1 在不同的NACK/NNACK，N=30比率下每個(gè)數(shù)據(jù)包的平均能耗

5 結(jié)束語

文中基于D2D 通信的多播考慮了從一個(gè)BS到一組BS 彼此靠近的設(shè)備，目的是將轉(zhuǎn)發(fā)器的能耗最小化。NACK 設(shè)備的關(guān)聯(lián)和轉(zhuǎn)發(fā)器傳輸功率的聯(lián)合優(yōu)化是一個(gè)MINLP 問題，針對(duì)這個(gè)問題提出了一種有效的算法，以找到好的關(guān)聯(lián)模式和傳輸功率。與具有固定數(shù)量的轉(zhuǎn)發(fā)器的算法相比，文中的轉(zhuǎn)發(fā)方案大大降低了轉(zhuǎn)發(fā)器的總能耗。此外，節(jié)能增益隨著多播接收器數(shù)量或ACK設(shè)備數(shù)量的增加而增加。