串行干擾抵消的靜態(tài)無線網(wǎng)絡(luò)上下文感知調(diào)度算法

呂紹和，王曉東，周興銘

（國防科技大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長沙 410073）

1 引言

串行干擾抵消(SIC, successive interference cancellation)[1]是一種有效對(duì)抗干擾的多分組接收(MPR, multiple packet reception) 技術(shù)。多分組接收技術(shù)是物理層的重要進(jìn)步，它試圖從沖突信號(hào)中解碼多個(gè)報(bào)文，從而消解沖突。然而，沖突信號(hào)只有在滿足一定條件時(shí)才可被解碼。因此，為確保MPR方法的可行性，需要細(xì)致協(xié)調(diào)網(wǎng)絡(luò)中各鏈路的傳輸。這就需要圍繞支持與利用 MPR而開展媒體接入控制層(MAC)與網(wǎng)絡(luò)層等上層協(xié)議的設(shè)計(jì)與研究。

具有SIC功能的接收節(jié)點(diǎn)使用迭代方式檢測(cè)多路傳輸信號(hào)。在每一次迭代檢測(cè)中，最強(qiáng)的信號(hào)被解碼，而其他信號(hào)被視為干擾。如果信號(hào)干擾噪聲比(SINR, signal to interference and noise ratio)不低于給定閾值，則該信號(hào)被解碼然后從混合信號(hào)中移除。在隨后的迭代檢測(cè)中，下一個(gè)最強(qiáng)的信號(hào)被解碼。這個(gè)迭代過程持續(xù)到所有的信號(hào)均被解碼或者迭代失敗。這種逐一解碼沖突信號(hào)的過程反映了SIC的順序檢測(cè)(sequential detection) 特性。

處理干擾是無線通信系統(tǒng)設(shè)計(jì)的主要難題之一?？紤]在鏈路L2的接收節(jié)點(diǎn)處，鏈路 L1對(duì)鏈路L2的影響。一方面，若 L1的信號(hào)強(qiáng)度雖弱于 L2，但兩者并發(fā)時(shí)，L2的信號(hào)SINR不能達(dá)到閾值，則L2的接收將因 L1的干擾而失敗。另一方面，若 L1的信號(hào)強(qiáng)度足夠強(qiáng)于L2，則SIC可首先解碼并移除L1的信號(hào)從而消除它對(duì)L2的干擾。但此時(shí)，第三方的信號(hào)可通過阻止L1信號(hào)的解碼來達(dá)到干擾L2的效果。此外，干擾的累積效應(yīng)(accumulative effect)也使得一個(gè)鏈路的干擾效果不單由其自身決定，還與其他并發(fā)鏈路緊密相關(guān)。累積效應(yīng)是指當(dāng)多份干擾信號(hào)并存時(shí)，總干擾為它們的累加。因此，在調(diào)度一條鏈路時(shí)，需要綜合所有先前已調(diào)度鏈路的影響，才能準(zhǔn)確地刻畫當(dāng)前鏈路的干擾效果。定義這些并發(fā)鏈路為當(dāng)前鏈路的上下文(context)?；诶鄯e干擾模型，本文研究了上下文感知的調(diào)度算法。

由于鏈路調(diào)度多為NP-hard問題，貪婪算法[2,3]作為一種有效的近似算法得到廣泛應(yīng)用。通常，貪婪鏈路調(diào)度算法主要包括2個(gè)階段：鏈路選擇與時(shí)間槽選擇。前者選擇下一個(gè)將被調(diào)度的鏈路，而后者則為當(dāng)前鏈路分配合適的時(shí)間槽。現(xiàn)有調(diào)度算法著重于鏈路選擇策略的研究，而在時(shí)間槽選擇階段采用簡單的首次匹配(first fit)策略。首次匹配是指對(duì)給定的鏈路L，從第一個(gè)時(shí)間槽開始，按序?qū)ふ铱煞峙浣oL的xL個(gè)時(shí)間槽(xL為L所需時(shí)間槽的數(shù)目，xL≥1)。在鏈路選擇階段，這些算法通過利用干擾信息來設(shè)計(jì)合理的選擇策略。然而，衡量鏈路的干擾狀況，需要知道它的上下文信息，這些信息在為鏈路分配時(shí)間槽之前無法獲知。因此，現(xiàn)有調(diào)度算法對(duì)鏈路干擾信息的獲取與利用都極不充分，這嚴(yán)重限制了它們的性能。

相關(guān)工作：無線網(wǎng)絡(luò)的干擾模型主要包括累積干擾模型[2]與非累積干擾模型[3]。已經(jīng)證明，在 2類模型下，無線網(wǎng)絡(luò)中的鏈路調(diào)度都是NP-hard問題[3]。因此，貪婪算法廣泛用于構(gòu)造近似最優(yōu)的調(diào)度，例如基于非累積干擾模型的調(diào)度[3]與基于累積干擾模型的調(diào)度[2]。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)具備多分組接收能力時(shí)，需要新的干擾模型以反映此時(shí)的干擾特征。在Celik等的工作中[4]，累積干擾模型得到了擴(kuò)展。此時(shí)，SINR閾值被設(shè)置為小于1的某個(gè)值，從而使得沖突信號(hào)中的多個(gè)報(bào)文可被解碼。該模型的缺陷在于它沒有考慮沖突中不同信號(hào)的差別，因而無法刻畫SIC的順序檢測(cè)特征。

Lv等[5]以非累積干擾模型為基礎(chǔ)，給出了一個(gè)刻畫SIC特征的干擾模型。它準(zhǔn)確捕捉了當(dāng)接收節(jié)點(diǎn)具有SIC能力時(shí)，并發(fā)的多條鏈路之間所存在的依賴性(correlation)。它的不足在于，未考慮無線干擾的累積效應(yīng)。此外，Gelal等[6]研究了支持SIC的多用戶 MIMO無線網(wǎng)絡(luò)中的拓?fù)淇刂?。最近，Lv等[7]提出沖突集圖(conflict set graph)以建模支持SIC時(shí)無線網(wǎng)絡(luò)中的干擾。但在最壞情況時(shí)，該方法的時(shí)間復(fù)雜度是指數(shù)級(jí)的。

主要貢獻(xiàn)：提出了一種新的貪婪算法，即上下文感知調(diào)度算法。首先，給出加權(quán)并發(fā)圖以描述支持SIC時(shí)無線網(wǎng)絡(luò)的干擾。然后，著重研究了時(shí)間槽選擇階段的設(shè)計(jì)，即對(duì)于給定鏈路，若存在多個(gè)可用時(shí)間槽，是否首次匹配的時(shí)間槽一定為最佳，或如何選擇最佳的時(shí)間槽？基于鏈路的上下文信息，定義容忍度以衡量鏈路集的飽和度(即接納新的鏈路的能力)并給出2種啟發(fā)式的策略：①選擇時(shí)間槽使得該時(shí)間槽鏈路集的容忍度最大；②選擇時(shí)間槽使得該時(shí)間槽鏈路集的容忍度變化最小。仿真結(jié)果表明，所提方案的性能優(yōu)于首次匹配策略。

本文的剩余部分組織如下。第2節(jié)描述系統(tǒng)模型，第3節(jié)與第4節(jié)分別給出加權(quán)并發(fā)圖與上下文感知貪婪調(diào)度算法，第5節(jié)給出仿真實(shí)驗(yàn)結(jié)果，第6節(jié)總結(jié)全文。

2 系統(tǒng)模型

考慮一個(gè)含N個(gè)靜態(tài)節(jié)點(diǎn)與n條鏈路的單信道無線網(wǎng)絡(luò)。鏈路標(biāo)記為 Li，其傳輸節(jié)點(diǎn)為 Si且接收節(jié)點(diǎn)為 Ri，其中， i = 1 ,2,… ,n 。假定：①SIC中信號(hào)的移除是無誤差的；②每一個(gè)節(jié)點(diǎn)配有一個(gè)全向天線，工作于半雙工模式且在同一時(shí)刻不能發(fā)送多個(gè)報(bào)文。

SIC的順序檢測(cè)：考慮2條鏈路 L1與 L2。當(dāng)在R1處，來自 L2的信號(hào)功率足夠強(qiáng)，使得在有 L1的信號(hào)干擾下， L2的信號(hào)仍能被 R1檢測(cè)。然后，通過移除 L2的信號(hào)， R1可完成對(duì) L1信號(hào)的解碼。此時(shí)，

稱1L依賴于2L且2L為1L的相關(guān)鏈路。所滿足條件是

其中，Pij是節(jié)點(diǎn) Ri處，來自節(jié)點(diǎn) Sj的信號(hào)的接收能量；N0為噪聲強(qiáng)度；βij為節(jié)點(diǎn)Ri解碼來自節(jié)點(diǎn)Sj的信號(hào)所需的最低SINR。

常用的無線干擾模型包括非累積模型與累積模型2類。前者僅考慮鏈路兩兩之間的關(guān)系，后者則考慮了干擾的累積效應(yīng)。累積干擾模型更真實(shí)反映了無線干擾的特點(diǎn)。為刻畫SIC的特征，下面給出一種模型。它對(duì)沖突中的所有鏈路，依據(jù)它們的信號(hào)強(qiáng)弱而排序，因此被稱為有序累積干擾模型(order-aware physical interference model)。

有序累積干擾模型：考慮 Ld的接收。設(shè)共有J( J ≤n-1)條與Ld并發(fā)的鏈路，其中D (D≤J)條是 Ld的相關(guān)鏈路。不失一般性，所有鏈路按照在Rd的接收功率排序?yàn)?Li1,Li2,… ,LiJ+1。假設(shè)ik= d ，則Piki1≥ Piki2≥ … ≥ PikiJ+1，相關(guān) 鏈路的集 合為{Li1,Li2,… ,LiD}。為成功檢測(cè)Ld的信號(hào)，要求

當(dāng)一組鏈路并發(fā)時(shí)，通過有序累積干擾模型，每條鏈路的傳輸成敗均可準(zhǔn)確判斷。當(dāng)鏈路集 LS并發(fā)時(shí)，若對(duì)任意鏈路 L∈LS，L的傳輸均成功，則稱LS為可行鏈路集(feasible link set)，簡稱為可行集。鏈路調(diào)度可轉(zhuǎn)化為尋找多個(gè)可行集的問題(詳見第4節(jié))。因此，下面討論如何建模網(wǎng)絡(luò)干擾及如何尋找可行集。

3 加權(quán)并發(fā)圖

圖是無線網(wǎng)絡(luò)十分常用的建模手段。Jain等[8]給出沖突圖(conflict graph)，它的每個(gè)頂點(diǎn)包含一條鏈路。當(dāng)2條鏈路不可并發(fā)時(shí)，相應(yīng)的2個(gè)頂點(diǎn)有邊相連。為反映干擾的累積效應(yīng)，Brar等[2]給出加權(quán)沖突圖(weighted conflict graph)，它的任意2頂點(diǎn)均相連，且權(quán)重設(shè)為鏈路之間的干擾強(qiáng)度。這些工作未考慮SIC的順序檢測(cè)特性。

Lv等[5]指出，對(duì)鏈路1L與2L，若它們的并發(fā)需要SIC的支持，則它們之間存在一種依賴關(guān)系。為此，Lv等引入一類新的圖頂點(diǎn)——超頂點(diǎn)(SV,super vertex)，它同時(shí)包含鏈路及其所依賴的鏈路。與之相比，普通頂點(diǎn)(OV, ordinary vertex)則僅包含單條鏈路。據(jù)此，Lv等提出并發(fā)圖(SG，simultaneity graph)以描述支持SIC時(shí)的網(wǎng)絡(luò)干擾。但是，并發(fā)圖未考慮無線干擾的累積效應(yīng)。

網(wǎng)絡(luò)干擾建模面臨的主要挑戰(zhàn)是處理SIC的順序檢測(cè)特性與干擾的累積效應(yīng)。下面給出加權(quán)并發(fā)圖(WSG，weighted simultaneity graph)。它的主要思想是通過權(quán)重反映鏈路之間的干擾，而權(quán)重之和則反映干擾的累積效應(yīng)。

3.1 構(gòu)造

具體地，令SGW=(V, E, WV, WE)表示一個(gè)WSG，其中，V為頂點(diǎn)集，E為有向邊的集合，WV與WE分別為點(diǎn)權(quán)(vertex weight)與邊權(quán)(edge weight)的集合。

SGW包含2類不同的頂點(diǎn)。

普通頂點(diǎn)對(duì)應(yīng)于單條鏈路。對(duì)鏈路 Li，建立OV (Li)。令 vi= Pii代表Li的權(quán)值。

對(duì)每條鏈路Li及其每條相關(guān)鏈路Lj，構(gòu)造SV(LiLj)。SV中鏈路的先后順序十分重要。例如，若Li依賴于Lj且Lj依賴于Li，則需要建立2個(gè)超頂點(diǎn)(LiLj)與(LjLi)。令 vij= Pij代表超頂點(diǎn)(LiLj)的權(quán)值。

SGW中有2類不同的邊。

建立Lj到Li的邊，若 Pij＜ ( Pii+ N0)βij(即 Lj不是Li的相關(guān)鏈路)。令 eij= Pij表示該邊的邊權(quán)。

建立 Lj到(LiLk)的邊，若 ( Pii+N0)βij≤Pij≤Pik(即Lj與Lk均為Li的相關(guān)鏈路，且在Ri處Lk的信號(hào)強(qiáng)于Lj的信號(hào))。令 eijk= Pij表示該邊的邊權(quán)。

與加權(quán)沖突圖不同，SGW中的頂點(diǎn)不需要兩兩相連。當(dāng)Lj是 Li的相關(guān)鏈路時(shí)，無需建立Lj到Li的邊。這是因?yàn)樵诠?jié)點(diǎn)Ri，Lj的信號(hào)先于Li的信號(hào)被解碼。在解碼Li的信號(hào)時(shí)，Lj的信號(hào)已被移除，不產(chǎn)生任何干擾。類似地，當(dāng)Lj與Lk均為Li的相關(guān)鏈路，且在Ri處Lk的信號(hào)強(qiáng)于Lj的信號(hào)，無需建立Lk到LiLj的邊。

圖1給出了加權(quán)并發(fā)圖的一個(gè)例子，圖1(a)為包含4條鏈路L1,…,L4的網(wǎng)絡(luò)，其中，L2與L3為L1的相關(guān)鏈路，且 S2、S3、S1與 S4到 R1的距離依次遞增。以鏈路L1為例說明SGW的構(gòu)造過程。首先，對(duì) 4條鏈路，建立 4個(gè)普通頂點(diǎn)(L1～L4)；由于 L2與L3為L1的相關(guān)鏈路，建立超頂點(diǎn)L1L2與L1L3。其次，由于鏈路L4并非L1的相關(guān)鏈路，建立L4到L1的邊，且邊權(quán)為 P14；由于L2與 L3為 L1的相關(guān)鏈路，無需建立L2與L3到L1的邊。由于P13＜P12，建立 L3到 L1L2的邊，且邊權(quán)為 P13；無需建立 L2到L1L3的邊。最后得到的加權(quán)并發(fā)圖如圖1(b)所示(為清晰起見，各頂點(diǎn)的權(quán)值未給出)。

圖1 加權(quán)并發(fā)圖的實(shí)例

3.2 討論

在給出調(diào)度算法之前，先簡要討論2個(gè)重要的問題：①加權(quán)并發(fā)圖的構(gòu)造方法；②SIC的實(shí)現(xiàn)復(fù)雜度等的考慮。

加權(quán)并發(fā)圖的構(gòu)造，關(guān)鍵在于接收能量Pij的獲取。對(duì)此，Qiu等[9]與Reis等[10]給出了一種基于測(cè)量的方法，它的基本思想是：當(dāng)沒有鏈路傳輸時(shí)，接收節(jié)點(diǎn)可測(cè)量到噪聲強(qiáng)度N0；對(duì)鏈路Lj，在某個(gè)時(shí)間槽上，僅允許Sj發(fā)送報(bào)文，此時(shí)對(duì)任意接收節(jié)點(diǎn)Ri，它所測(cè)量到的接收能量就是(N0+Pij)；對(duì)每條鏈路，均執(zhí)行該過程，就可得到所有的 Pij(1≤i,j≤n)。顯然，該方法對(duì)靜態(tài)無線網(wǎng)絡(luò)有效，一旦網(wǎng)絡(luò)拓?fù)涑霈F(xiàn)動(dòng)態(tài)變化，就需重新執(zhí)行以上的測(cè)量過程。當(dāng)網(wǎng)絡(luò)具有較強(qiáng)的動(dòng)態(tài)性時(shí)，該方法的開銷與時(shí)效性都變得很不理想。對(duì)動(dòng)態(tài)的無線網(wǎng)絡(luò)，如何及時(shí)地獲取它的狀態(tài)信息，本身仍是一個(gè)極具挑戰(zhàn)性的問題。就鏈路調(diào)度而言，當(dāng)網(wǎng)絡(luò)經(jīng)常動(dòng)態(tài)變化時(shí)，現(xiàn)有的調(diào)度策略可能并不適用。此時(shí)，需要某種機(jī)制對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)性予以跟蹤、分析與預(yù)測(cè)。這超出了本文的研究范圍。

SIC的思想十分簡單，但它的計(jì)算量、控制邏輯等實(shí)現(xiàn)上的復(fù)雜度不可輕視。硬件設(shè)計(jì)工藝及軟件無線電(SDR, software-defined radio)等新技術(shù)的進(jìn)步，有助于克服這方面的難題。最近，Halperin等[11]在SDR平臺(tái)實(shí)現(xiàn)了SIC并通過實(shí)驗(yàn)分析了SIC對(duì)網(wǎng)絡(luò)性能的影響。作為一種復(fù)雜的信號(hào)處理算法，SIC的實(shí)現(xiàn)最關(guān)鍵的地方是對(duì)性能與代價(jià)的取舍。Weber等[12]指出，僅需不超過2次的迭代解碼，SIC就能大幅度提高網(wǎng)絡(luò)性能；同時(shí)，繼續(xù)增大迭代解碼的次數(shù)，并不能顯著改善網(wǎng)絡(luò)性能。因此，SIC的實(shí)現(xiàn)可大大簡化。通過避免復(fù)雜的高階迭代，便能以少量的性能損失，換取實(shí)現(xiàn)難度的降低。

4 上下文感知的調(diào)度

由于干擾的累積效應(yīng)與SIC的順序檢測(cè)特性，除非鏈路的上下文已完全指定，否則難以精確評(píng)估鏈路干擾。這使得在鏈路選擇階段，可利用的干擾信息極為有限。為此，研究時(shí)間槽選擇階段干擾信息的利用并據(jù)此提出新的調(diào)度算法。

4.1 貪婪算法的一般過程

以TDMA(time division multiple access)為背景，研究鏈路調(diào)度(link scheduling)問題。TDMA將時(shí)間劃分為等長的時(shí)間槽(time slot)，每個(gè)時(shí)間槽可用以完成一個(gè)報(bào)文的傳輸。假設(shè)每條鏈路僅需要一個(gè)時(shí)間槽，鏈路調(diào)度問題是：給定加權(quán)并發(fā)圖，尋找一組鏈路集滿足：①每條鏈路均含于某一個(gè)鏈路集；②每個(gè)鏈路集均為可行集；③鏈路集的數(shù)目為最小。

定理1 在支持SIC的無線網(wǎng)絡(luò)中，基于累積干擾模型的鏈路調(diào)度問題為NP-hard。

證明 對(duì)于任意鏈路iL以及每一個(gè)ji≠，令閾值ijβ→∞。那么，iL除了需要的信號(hào)，不能解碼其他任何信號(hào)。該問題自然退化成無SIC的鏈路調(diào)度問題，這已在文獻(xiàn)[8]中證實(shí)為NP-hard問題。因此，作為更普遍的情況，本文的問題也是NP-hard。

證畢。

由于尚不存在NP-hard問題的多項(xiàng)式時(shí)間最優(yōu)解法，貪婪算法作為有效的近似方案得到廣泛的研究。貪婪調(diào)度主要包含鏈路選擇與時(shí)間槽選擇等 2個(gè)階段。圖2給出了貪婪調(diào)度的一般過程：①鏈路選擇，在未調(diào)度鏈路的集合中依據(jù)給定的指標(biāo)選擇一條鏈路，令Li表示該鏈路；②時(shí)間槽選擇，在已分配時(shí)間槽中尋找對(duì)Li可用的時(shí)間槽。一個(gè)時(shí)間槽對(duì) Li可用是指將 Li調(diào)度到該時(shí)間槽后，包括 Li的所有已調(diào)度鏈路均能成功傳輸，若不存在可用時(shí)間槽，則分配新的時(shí)間槽，若有多個(gè)可用時(shí)間槽，算法將為Li選擇最佳的時(shí)間槽。以上過程不斷重復(fù)至所有鏈路均被調(diào)度。

圖2 貪婪調(diào)度算法的流程

現(xiàn)有調(diào)度[2,3,7]在時(shí)間槽選擇階段多采用首次匹配策略，即總選擇第一個(gè)可用時(shí)間槽。它們?cè)噲D在鏈路選擇階段利用干擾信息以獲得良好性能。這種設(shè)計(jì)的合理性來源于對(duì)圖著色(graph coloring)問題的研究。圖著色是圖論的經(jīng)典問題，它的研究結(jié)果指出，通過合理排序頂點(diǎn)，基于首次匹配的貪婪算法可得到最優(yōu)或近似最優(yōu)的解[7]。然而，圖模型只考慮了鏈路兩兩之間的干擾，這在非累積干擾模型下是可行的。但在累積干擾模型下，鏈路干擾的影響還與它的并發(fā)鏈路緊密相關(guān)。在鏈路選擇階段，這些并發(fā)鏈路即上下文，還無法確定，這嚴(yán)重限制了調(diào)度算法的性能。

據(jù)此，提出上下文感知的調(diào)度并著眼于時(shí)間槽選擇階段的設(shè)計(jì)。新方案的基本思想是，即使以任意方式排序鏈路，通過設(shè)計(jì)合適的時(shí)間槽選擇策略也能得到好的調(diào)度。此時(shí)，算法設(shè)計(jì)的主要任務(wù)是合理評(píng)估每個(gè)時(shí)間槽是否適合于調(diào)度當(dāng)前鏈路。該評(píng)估的關(guān)鍵在于準(zhǔn)確刻畫當(dāng)前鏈路被調(diào)度后所產(chǎn)生的干擾。此時(shí)，每個(gè)時(shí)間槽上已調(diào)度的鏈路，提供了評(píng)估當(dāng)前鏈路所需要的上下文信息。

4.2 鏈路集的飽和度

不妨記 Ski為在調(diào)度鏈路 Li前調(diào)度到時(shí)間槽 tk的鏈路集。則將Li調(diào)度到tk上所產(chǎn)生的干擾就體現(xiàn)為 Ski∪{Li}與 Ski在飽和度(即接納新鏈路的能力)上的差異。對(duì)鏈路集LS與鏈路L，若 L S∪{L}為不可行集時(shí)，稱鏈路集LS對(duì)于L飽和。顯然，空集合的飽和度最小。任何新鏈路的加入都可能增大鏈路集的飽和度。但若新鏈路的干擾可通過SIC消除，則它的加入并不會(huì)改變鏈路集的飽和度。鏈路集LS的飽和度通過LS中的鏈路的抗干擾能力體現(xiàn)。

定義1 鏈路L∈LS的容忍度(tolerance margin)是指當(dāng)LS的所有鏈路并發(fā)時(shí)，鏈路L所能容忍的最大干擾。

給定加權(quán)并發(fā)圖，算法1給出了容忍度的計(jì)算過程。該容忍度是以下干擾值的較小者：①干擾L的任意一條相關(guān)鏈路的信號(hào)解碼所需的最小干擾；②在所有相關(guān)鏈路的信號(hào)均被移除后，干擾L的信號(hào)解碼所需的最小干擾。算法的 2)～3)行計(jì)算第②部分，而4)～10)行則計(jì)算了第①部分。鏈路的容忍度與可行性存在以下關(guān)系，其正確性不難證明。

定理2 鏈路集LS中的鏈路L可行，當(dāng)且僅當(dāng)L的容忍度大于0。

定理3 算法1的時(shí)間復(fù)雜度為O(|LS|2)，其中，|LS|為LS所含鏈路的數(shù)目。

證明 首先，第 2行需要遍歷頂點(diǎn) Li與 Lx(Lx∈LS)之間的邊，其復(fù)雜度不超過O(|LS|)。其次，第 4)～10)行需要遍歷所有形如 LiLy(Ly∈LS)的超頂點(diǎn)及其與 Lx(Lx∈LS)的邊。每個(gè)超頂點(diǎn)的邊數(shù)不超過O(|LS|)，而超頂點(diǎn)的數(shù)目不超過O(|LS|)。因而，復(fù)雜度不超過 O(|LS|2)，即算法的時(shí)間復(fù)雜度為O(|LS|2)。 證畢。

算法1 容忍度的計(jì)算

輸入：SGW=(V,E,WV,WE)：加權(quán)并發(fā)圖

LS：鏈路集; Li：LS中的鏈路

輸出： Li的容忍度

以圖1中鏈路L1為例說明容忍度的計(jì)算。首先，移除相關(guān)鏈路的信號(hào)后，L1所受干擾為L4的信號(hào)與噪聲。從而L1還能承受的干擾為M1=P11/11β-N0-P14。其次，考慮R1對(duì)相關(guān)鏈路信號(hào)的解碼。對(duì)鏈路L2，鏈路L1與另一條相關(guān)鏈路L3的信號(hào)均為干擾，它的信號(hào)解碼還能承受的干擾為M2=P12/β12-N0-P14-P13-P11。類似地，對(duì)鏈路L3，它的信號(hào)解碼還能承受的干擾為M3=P13/β13-N0- P14-P11。最終，鏈路L1的容忍度為{M1, M2, M3}的最小值。

定義2 鏈路集LS的容忍度，記為 MLS，是指它在可行的前提下所能容忍的最大干擾。

集合的容忍度是其每條鏈路容忍度的最小值。鏈路集容忍度的計(jì)算方法如下：對(duì)鏈路集的每條鏈路應(yīng)用算法 1，然后取所有結(jié)果中的最小值。對(duì)L?LS，若有 MLS∪{L}≥0，則稱LS對(duì)L可行。容忍度衡量了鏈路集的飽和度?？占系娜萑潭葹闊o窮大。新鏈路的加入，將可能導(dǎo)致容忍度的降低與飽和度的增加。最終，當(dāng)容忍度降低到一個(gè)臨界點(diǎn)，任何未調(diào)度鏈路的加入都將使得鏈路集為不可行，就稱鏈路集達(dá)到飽和。類似地，對(duì)鏈路集的容忍度與可行性，存在如下關(guān)系。

定理4 鏈路集LS可行，當(dāng)且僅當(dāng)LS的容忍度大于0。

首次匹配策略的次優(yōu)性在于其簡單選擇第一個(gè)可行的時(shí)間槽，而忽略了時(shí)間槽上所調(diào)度鏈路集的容忍度?？紤] 2條鏈路 L1與 L2，假設(shè)P12/(N0+ P11) = β12。由于SIC可在L1的接收節(jié)點(diǎn)移除L2的信號(hào)，L1與L2可并發(fā)。但若它們并發(fā)，由于 M{L1,L2}= 0 ，任何其他鏈路都不能再調(diào)度到該時(shí)間槽上。從全網(wǎng)優(yōu)化的角度看，將兩者分配到不同時(shí)間槽，或許能得到更好的結(jié)果。因此，任意方式選擇時(shí)間槽可能會(huì)增大最終所需的時(shí)間槽數(shù)目。

4.3 上下文感知調(diào)度

現(xiàn)在給出上下文感知的調(diào)度算法CONG，其過程如算法 2所示。首先將所有鏈路任意排序?yàn)閘1, l2,… ,ln。在li調(diào)度之前，令Ni為已用時(shí)間槽的數(shù)目，Sij為在第j個(gè)時(shí)間槽上所調(diào)度的鏈路集。CONG按如下方式從l1開始依次處理每一條鏈路：①對(duì)每個(gè)計(jì)算的容忍度；②若Ni=0或?qū)λ? ≤ j≤ Ni，Sij對(duì) li均不可行，則分配新時(shí)間槽以調(diào)度 li。否則，在所有可用時(shí)間槽中選擇一個(gè)以調(diào)度 li。在處理完所有鏈路后，CONG返回總時(shí)間槽數(shù)目與每個(gè)時(shí)間槽上所調(diào)度的鏈路集。顯然，所有鏈路集均為可行集。

算法2 上下文感知貪婪調(diào)度算法CONG

輸入：SGW=(V,E,WV,WE)：加權(quán)并發(fā)圖

輸出：時(shí)間槽的數(shù)目M及調(diào)度S1,…,SM

定理5 算法2的時(shí)間復(fù)雜度不超過O(n3)，其中n為網(wǎng)絡(luò)所含鏈路的數(shù)目。

證明 首先，對(duì)任意的鏈路集Sk，計(jì)算它的容忍度，時(shí)間開銷不超過 O(|Sk|2)。同時(shí)，注意到而所有 Sk的鏈路總數(shù)不超過 O(n)。因此，第 4)～6)行的總時(shí)間開銷不超過 O(n2)。其次，第 7)～10)行的時(shí)間開銷為常數(shù)，而第 11)行所需的容忍度信息已被計(jì)算，選擇過程的開銷為 O(M)≤O(n)?？傊淮窝h(huán)(第 4)～11)行)所需時(shí)間為 O(n2)。循環(huán)執(zhí)行的次數(shù)不超過O(n)。從而，總的時(shí)間開銷不超過 O(n3)。

證畢。

下面給出2種選擇時(shí)間槽的策略。

最大殘余優(yōu)先（LRF, largest residue first）：在所有可用時(shí)間槽中，選擇具有最大容忍度的第一個(gè)時(shí)間槽。對(duì)鏈路 li，選擇第k個(gè)時(shí)間槽的條件：k是 TliΔ中的最小值，

最小減量優(yōu)先（MDF, minimum decrease first）：在所有可用時(shí)間槽中，選擇容忍度降低最小的第一個(gè)時(shí)間槽。對(duì)鏈路li，選擇第k個(gè)時(shí)間槽的條件：k是ilTδ中的最小值，

2種策略的共同目標(biāo)是將更多的鏈路調(diào)度到已選的時(shí)間槽中。一般地，容忍度越大，鏈路集接收新鏈路的能力越強(qiáng)。LRF的選擇平衡了不同時(shí)間槽上的容忍度，避免在調(diào)度早期就導(dǎo)致大量時(shí)間槽上的鏈路集達(dá)到飽和。而MDF則更著眼于最小化當(dāng)前鏈路被調(diào)度所產(chǎn)生的干擾。圖3給出的例子展示了LRF與MDF的區(qū)別，假設(shè)調(diào)度il之前已使用 3個(gè)時(shí)間槽。由于LRF選擇1t時(shí)間槽。然而，由于MDF選擇3t時(shí)間槽。下面通過仿真實(shí)驗(yàn)考察 2種策略的性能。

圖3 LRF與MDF區(qū)別的例子

5 性能評(píng)估

通過網(wǎng)絡(luò)仿真器(NS 2, network simulator 2)[13]的仿真實(shí)驗(yàn)評(píng)價(jià)了近似方案的性能。表1總結(jié)了仿真過程中參數(shù)和協(xié)議的設(shè)置。評(píng)測(cè)性能指標(biāo)為吞吐量，其中，平均吞吐量為總吞吐量(aggregate throughput)的平均，平均鏈路吞吐量為單條鏈路所獲得的吞吐量的平均值。每一個(gè)數(shù)據(jù)點(diǎn)都是通過對(duì)多次運(yùn)行結(jié)果取平均值獲得。通過與首次匹配策略的比較來考察新調(diào)度機(jī)制的性能。2種新策略與首次匹配的實(shí)驗(yàn)結(jié)果分別用 LRF、MDF與 First-Fit表示。

NS 2并未提供對(duì)基于SINR模型的報(bào)文接收與SIC功能的支持。首先增加新的模塊以支持累積干擾模型與SIC，詳細(xì)描述可參考文獻(xiàn)[5,7]。表1中的傳輸范圍是指無其他并發(fā)傳輸時(shí)鏈路能正常通信的最大距離。若無特別說明，在每個(gè)時(shí)間槽的開始，每個(gè)源節(jié)點(diǎn)都依概率η發(fā)出一個(gè)報(bào)文。該概率對(duì)所有源節(jié)點(diǎn)均相同。

表1 仿真參數(shù)

首先在單跳情況下評(píng)估調(diào)度算法的性能。在150m×150m的區(qū)域內(nèi)，隨機(jī)分布100個(gè)節(jié)點(diǎn)并隨機(jī)選取其中25個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)。圖4給出3種算法所得到的吞吐量。作為參考，利用數(shù)學(xué)規(guī)劃可得到此時(shí)的最大吞吐量，用Optimal表示。LRF與MDF的表現(xiàn)很好。相比于First fit策略，LRF與MDF在吞吐量上的優(yōu)勢(shì)高達(dá)30%。此外，隨著傳輸概率的增大，F(xiàn)irst-fit的吞吐量急劇下降。這是因?yàn)閷?shí)驗(yàn)中鏈路以任意方式排序，當(dāng)鏈路的數(shù)目很大時(shí)，每條鏈路的時(shí)間槽以First-fit方式任意選擇，導(dǎo)致最終的調(diào)度性能很不理想。LRF與MDF的性能基本相當(dāng)。但是，也必須看到，3種近似算法與優(yōu)化值均有一定距離，設(shè)計(jì)更好的時(shí)間槽選擇機(jī)制仍需進(jìn)一步研究。

圖4 單跳網(wǎng)絡(luò)中平均吞吐量與傳輸概率的關(guān)系

為考察在較大規(guī)模的網(wǎng)絡(luò)中SIC的效果，在一個(gè)500m×500m的區(qū)域內(nèi)，均勻部署81個(gè)節(jié)點(diǎn)并隨機(jī)選取其中30個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)。對(duì)每個(gè)源節(jié)點(diǎn)，在其通信范圍內(nèi)隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)。圖5給出平均吞吐量與傳輸概率η之間的關(guān)系?？紤]另一種流模式，令(x, y) (1≤x≤9, 1≤y≤9)表示不同位置的節(jié)點(diǎn)，考慮以下3種流模式：①P1:(x, 1)→(x, 9)；②X1: (x, 2)→((x+7) mod 9, 7)；③X2: (x, 9)→((x+7) mod 9, 1)。v1 mod v2 為取模運(yùn)算，它返回v1除以v2的余數(shù)。每種流模式下均有9個(gè)不同的數(shù)據(jù)流。這些數(shù)據(jù)流可能需要多跳傳輸。不同流模式下，所需的轉(zhuǎn)發(fā)鏈路數(shù)也不同。其中，P1所需鏈路數(shù)最小，X1次之，而X2所需最多。圖6給出了3種流模式的吞吐量。

圖5對(duì)應(yīng)的場景中，隨著η的增長，活躍鏈路的數(shù)目將逐漸增大。圖 6對(duì)應(yīng)的場景中，從 P1、X1到X2，總鏈路數(shù)目亦不斷增多。隨著網(wǎng)絡(luò)包含越來越多的鏈路，可以預(yù)期在網(wǎng)絡(luò)中將存在更多并發(fā)傳輸?shù)臋C(jī)會(huì)。這些場景中，LRF與MDF展示出了明顯優(yōu)于First-fit的性能。

圖5 81節(jié)點(diǎn)均勻分布的網(wǎng)絡(luò)中平均鏈路吞吐量與傳輸概率的關(guān)系

圖6 81節(jié)點(diǎn)均勻分布的網(wǎng)絡(luò)中不同流模式時(shí)的平均鏈路吞吐量

最后，在一個(gè) 500m×500m的區(qū)域內(nèi)隨機(jī)方式部署100個(gè)節(jié)點(diǎn)。然后隨機(jī)選取其中的30個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)。對(duì)每個(gè)源節(jié)點(diǎn)，以隨機(jī)方式選擇目標(biāo)節(jié)點(diǎn)。此時(shí)，一些節(jié)點(diǎn)對(duì)的傳輸需要多跳路由，所有活躍鏈路的總數(shù)在 30～48之間。圖 7給出了在η= 0 .8時(shí)，平均吞吐量與鏈路數(shù)目的關(guān)系。與First-fit相比，LRF與MDF的吞吐量增益可達(dá)27%。

圖7 100個(gè)節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)中平均鏈路吞吐量與鏈路數(shù)目的關(guān)系

6 結(jié)束語

本文研究了支持 SIC的靜態(tài)無線網(wǎng)絡(luò)中基于累積干擾模型的鏈路調(diào)度。首先給出加權(quán)并發(fā)圖以描述網(wǎng)絡(luò)干擾，并指出鏈路調(diào)度為NP-hard問題。然后，重點(diǎn)研究了貪婪調(diào)度算法。由于SIC的順序檢測(cè)特性與干擾的累積效應(yīng)，如何準(zhǔn)確衡量鏈路干擾是主要的研究挑戰(zhàn)?，F(xiàn)有的貪婪調(diào)度方法不能充分地理解與利用干擾信息，導(dǎo)致它們的性能不夠理想。本文定義了容忍度以衡量鏈路集的飽和度，然后給出2個(gè)高效的策略為給定的鏈路選擇最佳時(shí)間槽。在仿真實(shí)驗(yàn)中，2種策略的性能均優(yōu)于常用的首次匹配策略。

[1] ANDREWS J. Interference cancellation for cellular systems: a contemporary overview[J]. IEEE Wireless Communications, 2005, 12(2): 19-29.

[2] BRAR G, BLOUGH D, SANTI P. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks[A]. ACM MOBICOM’06[C]. Los Angeles,USA, 2006. 2-13.

[3] WANG W, LI X, FRIEDER O, et al. Efficient interference-aware TDMA link scheduling for static wireless networks[A]. ACM MOBICOM’06[C]. Los Angeles, USA, 2006. 262-273.

[4] CELIK G, ZUSSMAN G, KHAN W, et al. MAC for networks with multipacket reception capability and spatially distributed nodes[A].IEEE INFOCOM’08[C]. Phoenix, USA, 2008. 1436-1444.

[5] LV S, ZHUANG W, WANG X, et al. Scheduling in wireless ad hoc networks with successive interference cancellation[A]. IEEE INFOCOM’11[C]. Shanghai, China, 2011. 1282-1290.

[6] GELAL E, PELECHRINIS K, KIM T, et al. Topology control for effective interference cancellation in multi-user MIMO networks[A].IEEE INFOCOM’10[C]. San Diego, USA, 2010. 2357-2365.

[7] LV S, WANG X, ZHOU X. Scheduling under SINR model in ad hoc networks with successive interference cancellation[A]. IEEE GLOBECOM’10[C]. Miami, USA, 2010. 1-5.

[8] JIAN K, PADHYE J, PADMANABHAN V, et al. Impact of interference on multi-hop wireless network performance[A]. ACM MOBICOM’03[C]. San Diego, USA, 2003. 66-80.

[9] QIU L, ZHANG Y, WANG F, et al. A general model of wireless interference[A]. ACM MOBICOM’07[C]. Montreal, Canada, 2007. 171-182.

[10] REIS C, MAHAJAN R, RODRIG M, et al. Measurement-based models of delivery and interference in static wireless networks[A]. ACM SIGCOMM’06[C]. Pisa, Italy, 2006. 51-62.

[11] HALPERIN D, ANDERSON T, WETHRALL D. Taking the sting out of carrier sense: interference cancellation for wireless LANs[A]. ACMMOBICOM’08[C]. San Francisco, USA, 2008. 339-350.

[12] WEBER S, ANDREWS J, YANG X, et al. Transmission capacity of wireless ad hoc networks with successive interference cancellation[J].IEEE Trans Information Theory, 2007, 53(8): 2799-2814.

[13] NS-2, Network simulator version 2[EB/OL]. http://www.isi.edu/nsnam/ns/ [EB/OL]. 2010.