串行干扰抵消的静态无线网络上下文感知调度算法

吕绍和，王晓东，周兴铭

（国防科技大学 计算机学院，湖南 长沙 410073）

1 引言

串行干扰抵消(SIC, successive interference cancellation)[1]是一种有效对抗干扰的多分组接收(MPR, multiple packet reception) 技术。多分组接收技术是物理层的重要进步，它试图从冲突信号中解码多个报文，从而消解冲突。然而，冲突信号只有在满足一定条件时才可被解码。因此，为确保MPR方法的可行性，需要细致协调网络中各链路的传输。这就需要围绕支持与利用 MPR而开展媒体接入控制层(MAC)与网络层等上层协议的设计与研究。

具有SIC功能的接收节点使用迭代方式检测多路传输信号。在每一次迭代检测中，最强的信号被解码，而其他信号被视为干扰。如果信号干扰噪声比(SINR, signal to interference and noise ratio)不低于给定阈值，则该信号被解码然后从混合信号中移除。在随后的迭代检测中，下一个最强的信号被解码。这个迭代过程持续到所有的信号均被解码或者迭代失败。这种逐一解码冲突信号的过程反映了SIC的顺序检测(sequential detection) 特性。

处理干扰是无线通信系统设计的主要难题之一。考虑在链路L2的接收节点处，链路 L1对链路L2的影响。一方面，若 L1的信号强度虽弱于 L2，但两者并发时，L2的信号SINR不能达到阈值，则L2的接收将因 L1的干扰而失败。另一方面，若 L1的信号强度足够强于L2，则SIC可首先解码并移除L1的信号从而消除它对L2的干扰。但此时，第三方的信号可通过阻止L1信号的解码来达到干扰L2的效果。此外，干扰的累积效应(accumulative effect)也使得一个链路的干扰效果不单由其自身决定，还与其他并发链路紧密相关。累积效应是指当多份干扰信号并存时，总干扰为它们的累加。因此，在调度一条链路时，需要综合所有先前已调度链路的影响，才能准确地刻画当前链路的干扰效果。定义这些并发链路为当前链路的上下文(context)。基于累积干扰模型，本文研究了上下文感知的调度算法。

由于链路调度多为NP-hard问题，贪婪算法[2,3]作为一种有效的近似算法得到广泛应用。通常，贪婪链路调度算法主要包括2个阶段：链路选择与时间槽选择。前者选择下一个将被调度的链路，而后者则为当前链路分配合适的时间槽。现有调度算法着重于链路选择策略的研究，而在时间槽选择阶段采用简单的首次匹配(first fit)策略。首次匹配是指对给定的链路L，从第一个时间槽开始，按序寻找可分配给L的xL个时间槽(xL为L所需时间槽的数目，xL≥1)。在链路选择阶段，这些算法通过利用干扰信息来设计合理的选择策略。然而，衡量链路的干扰状况，需要知道它的上下文信息，这些信息在为链路分配时间槽之前无法获知。因此，现有调度算法对链路干扰信息的获取与利用都极不充分，这严重限制了它们的性能。

相关工作：无线网络的干扰模型主要包括累积干扰模型[2]与非累积干扰模型[3]。已经证明，在 2类模型下，无线网络中的链路调度都是NP-hard问题[3]。因此，贪婪算法广泛用于构造近似最优的调度，例如基于非累积干扰模型的调度[3]与基于累积干扰模型的调度[2]。当网络节点具备多分组接收能力时，需要新的干扰模型以反映此时的干扰特征。在Celik等的工作中[4]，累积干扰模型得到了扩展。此时，SINR阈值被设置为小于1的某个值，从而使得冲突信号中的多个报文可被解码。该模型的缺陷在于它没有考虑冲突中不同信号的差别，因而无法刻画SIC的顺序检测特征。

Lv等[5]以非累积干扰模型为基础，给出了一个刻画SIC特征的干扰模型。它准确捕捉了当接收节点具有SIC能力时，并发的多条链路之间所存在的依赖性(correlation)。它的不足在于，未考虑无线干扰的累积效应。此外，Gelal等[6]研究了支持SIC的多用户 MIMO无线网络中的拓扑控制。最近，Lv等[7]提出冲突集图(conflict set graph)以建模支持SIC时无线网络中的干扰。但在最坏情况时，该方法的时间复杂度是指数级的。

主要贡献：提出了一种新的贪婪算法，即上下文感知调度算法。首先，给出加权并发图以描述支持SIC时无线网络的干扰。然后，着重研究了时间槽选择阶段的设计，即对于给定链路，若存在多个可用时间槽，是否首次匹配的时间槽一定为最佳，或如何选择最佳的时间槽？基于链路的上下文信息，定义容忍度以衡量链路集的饱和度(即接纳新的链路的能力)并给出2种启发式的策略：①选择时间槽使得该时间槽链路集的容忍度最大；②选择时间槽使得该时间槽链路集的容忍度变化最小。仿真结果表明，所提方案的性能优于首次匹配策略。

本文的剩余部分组织如下。第2节描述系统模型，第3节与第4节分别给出加权并发图与上下文感知贪婪调度算法，第5节给出仿真实验结果，第6节总结全文。

2 系统模型

考虑一个含N个静态节点与n条链路的单信道无线网络。链路标记为 Li，其传输节点为 Si且接收节点为 Ri，其中， i = 1 ,2,… ,n 。假定：①SIC中信号的移除是无误差的；②每一个节点配有一个全向天线，工作于半双工模式且在同一时刻不能发送多个报文。

SIC的顺序检测：考虑2条链路 L1与 L2。当在R1处，来自 L2的信号功率足够强，使得在有 L1的信号干扰下， L2的信号仍能被 R1检测。然后，通过移除 L2的信号， R1可完成对 L1信号的解码。此时，

称1L依赖于2L且2L为1L的相关链路。所满足条件是

其中，Pij是节点 Ri处，来自节点 Sj的信号的接收能量；N0为噪声强度；βij为节点Ri解码来自节点Sj的信号所需的最低SINR。

常用的无线干扰模型包括非累积模型与累积模型2类。前者仅考虑链路两两之间的关系，后者则考虑了干扰的累积效应。累积干扰模型更真实反映了无线干扰的特点。为刻画SIC的特征，下面给出一种模型。它对冲突中的所有链路，依据它们的信号强弱而排序，因此被称为有序累积干扰模型(order-aware physical interference model)。

有序累积干扰模型：考虑 Ld的接收。设共有J( J ≤n-1)条与Ld并发的链路，其中D (D≤J)条是 Ld的相关链路。不失一般性，所有链路按照在Rd的接收功率排序为 Li1,Li2,… ,LiJ+1。假设ik= d ，则Piki1≥ Piki2≥ … ≥ PikiJ+1，相关 链路的集 合为{Li1,Li2,… ,LiD}。为成功检测Ld的信号，要求

当一组链路并发时，通过有序累积干扰模型，每条链路的传输成败均可准确判断。当链路集 LS并发时，若对任意链路 L∈LS，L的传输均成功，则称LS为可行链路集(feasible link set)，简称为可行集。链路调度可转化为寻找多个可行集的问题(详见第4节)。因此，下面讨论如何建模网络干扰及如何寻找可行集。

3 加权并发图

图是无线网络十分常用的建模手段。Jain等[8]给出冲突图(conflict graph)，它的每个顶点包含一条链路。当2条链路不可并发时，相应的2个顶点有边相连。为反映干扰的累积效应，Brar等[2]给出加权冲突图(weighted conflict graph)，它的任意2顶点均相连，且权重设为链路之间的干扰强度。这些工作未考虑SIC的顺序检测特性。

Lv等[5]指出，对链路1L与2L，若它们的并发需要SIC的支持，则它们之间存在一种依赖关系。为此，Lv等引入一类新的图顶点——超顶点(SV,super vertex)，它同时包含链路及其所依赖的链路。与之相比，普通顶点(OV, ordinary vertex)则仅包含单条链路。据此，Lv等提出并发图(SG，simultaneity graph)以描述支持SIC时的网络干扰。但是，并发图未考虑无线干扰的累积效应。

网络干扰建模面临的主要挑战是处理SIC的顺序检测特性与干扰的累积效应。下面给出加权并发图(WSG，weighted simultaneity graph)。它的主要思想是通过权重反映链路之间的干扰，而权重之和则反映干扰的累积效应。

3.1 构造

具体地，令SGW=(V, E, WV, WE)表示一个WSG，其中，V为顶点集，E为有向边的集合，WV与WE分别为点权(vertex weight)与边权(edge weight)的集合。

SGW包含2类不同的顶点。

普通顶点对应于单条链路。对链路 Li，建立OV (Li)。令 vi= Pii代表Li的权值。

对每条链路Li及其每条相关链路Lj，构造SV(LiLj)。SV中链路的先后顺序十分重要。例如，若Li依赖于Lj且Lj依赖于Li，则需要建立2个超顶点(LiLj)与(LjLi)。令 vij= Pij代表超顶点(LiLj)的权值。

SGW中有2类不同的边。

建立Lj到Li的边，若 Pij＜ ( Pii+ N0)βij(即 Lj不是Li的相关链路)。令 eij= Pij表示该边的边权。

建立 Lj到(LiLk)的边，若 ( Pii+N0)βij≤Pij≤Pik(即Lj与Lk均为Li的相关链路，且在Ri处Lk的信号强于Lj的信号)。令 eijk= Pij表示该边的边权。

与加权冲突图不同，SGW中的顶点不需要两两相连。当Lj是 Li的相关链路时，无需建立Lj到Li的边。这是因为在节点Ri，Lj的信号先于Li的信号被解码。在解码Li的信号时，Lj的信号已被移除，不产生任何干扰。类似地，当Lj与Lk均为Li的相关链路，且在Ri处Lk的信号强于Lj的信号，无需建立Lk到LiLj的边。

图1给出了加权并发图的一个例子，图1(a)为包含4条链路L1,…,L4的网络，其中，L2与L3为L1的相关链路，且 S2、S3、S1与 S4到 R1的距离依次递增。以链路L1为例说明SGW的构造过程。首先，对 4条链路，建立 4个普通顶点(L1～L4)；由于 L2与L3为L1的相关链路，建立超顶点L1L2与L1L3。其次，由于链路L4并非L1的相关链路，建立L4到L1的边，且边权为 P14；由于L2与 L3为 L1的相关链路，无需建立L2与L3到L1的边。由于P13＜P12，建立 L3到 L1L2的边，且边权为 P13；无需建立 L2到L1L3的边。最后得到的加权并发图如图1(b)所示(为清晰起见，各顶点的权值未给出)。

图1 加权并发图的实例

3.2 讨论

在给出调度算法之前，先简要讨论2个重要的问题：①加权并发图的构造方法；②SIC的实现复杂度等的考虑。

加权并发图的构造，关键在于接收能量Pij的获取。对此，Qiu等[9]与Reis等[10]给出了一种基于测量的方法，它的基本思想是：当没有链路传输时，接收节点可测量到噪声强度N0；对链路Lj，在某个时间槽上，仅允许Sj发送报文，此时对任意接收节点Ri，它所测量到的接收能量就是(N0+Pij)；对每条链路，均执行该过程，就可得到所有的 Pij(1≤i,j≤n)。显然，该方法对静态无线网络有效，一旦网络拓扑出现动态变化，就需重新执行以上的测量过程。当网络具有较强的动态性时，该方法的开销与时效性都变得很不理想。对动态的无线网络，如何及时地获取它的状态信息，本身仍是一个极具挑战性的问题。就链路调度而言，当网络经常动态变化时，现有的调度策略可能并不适用。此时，需要某种机制对网络的动态性予以跟踪、分析与预测。这超出了本文的研究范围。

SIC的思想十分简单，但它的计算量、控制逻辑等实现上的复杂度不可轻视。硬件设计工艺及软件无线电(SDR, software-defined radio)等新技术的进步，有助于克服这方面的难题。最近，Halperin等[11]在SDR平台实现了SIC并通过实验分析了SIC对网络性能的影响。作为一种复杂的信号处理算法，SIC的实现最关键的地方是对性能与代价的取舍。Weber等[12]指出，仅需不超过2次的迭代解码，SIC就能大幅度提高网络性能；同时，继续增大迭代解码的次数，并不能显著改善网络性能。因此，SIC的实现可大大简化。通过避免复杂的高阶迭代，便能以少量的性能损失，换取实现难度的降低。

4 上下文感知的调度

由于干扰的累积效应与SIC的顺序检测特性，除非链路的上下文已完全指定，否则难以精确评估链路干扰。这使得在链路选择阶段，可利用的干扰信息极为有限。为此，研究时间槽选择阶段干扰信息的利用并据此提出新的调度算法。

4.1 贪婪算法的一般过程

以TDMA(time division multiple access)为背景，研究链路调度(link scheduling)问题。TDMA将时间划分为等长的时间槽(time slot)，每个时间槽可用以完成一个报文的传输。假设每条链路仅需要一个时间槽，链路调度问题是：给定加权并发图，寻找一组链路集满足：①每条链路均含于某一个链路集；②每个链路集均为可行集；③链路集的数目为最小。

定理1 在支持SIC的无线网络中，基于累积干扰模型的链路调度问题为NP-hard。

证明 对于任意链路iL以及每一个ji≠，令阈值ijβ→∞。那么，iL除了需要的信号，不能解码其他任何信号。该问题自然退化成无SIC的链路调度问题，这已在文献[8]中证实为NP-hard问题。因此，作为更普遍的情况，本文的问题也是NP-hard。

证毕。

由于尚不存在NP-hard问题的多项式时间最优解法，贪婪算法作为有效的近似方案得到广泛的研究。贪婪调度主要包含链路选择与时间槽选择等 2个阶段。图2给出了贪婪调度的一般过程：①链路选择，在未调度链路的集合中依据给定的指标选择一条链路，令Li表示该链路；②时间槽选择，在已分配时间槽中寻找对Li可用的时间槽。一个时间槽对 Li可用是指将 Li调度到该时间槽后，包括 Li的所有已调度链路均能成功传输，若不存在可用时间槽，则分配新的时间槽，若有多个可用时间槽，算法将为Li选择最佳的时间槽。以上过程不断重复至所有链路均被调度。

图2 贪婪调度算法的流程

现有调度[2,3,7]在时间槽选择阶段多采用首次匹配策略，即总选择第一个可用时间槽。它们试图在链路选择阶段利用干扰信息以获得良好性能。这种设计的合理性来源于对图着色(graph coloring)问题的研究。图着色是图论的经典问题，它的研究结果指出，通过合理排序顶点，基于首次匹配的贪婪算法可得到最优或近似最优的解[7]。然而，图模型只考虑了链路两两之间的干扰，这在非累积干扰模型下是可行的。但在累积干扰模型下，链路干扰的影响还与它的并发链路紧密相关。在链路选择阶段，这些并发链路即上下文，还无法确定，这严重限制了调度算法的性能。

据此，提出上下文感知的调度并着眼于时间槽选择阶段的设计。新方案的基本思想是，即使以任意方式排序链路，通过设计合适的时间槽选择策略也能得到好的调度。此时，算法设计的主要任务是合理评估每个时间槽是否适合于调度当前链路。该评估的关键在于准确刻画当前链路被调度后所产生的干扰。此时，每个时间槽上已调度的链路，提供了评估当前链路所需要的上下文信息。

4.2 链路集的饱和度

不妨记 Ski为在调度链路 Li前调度到时间槽 tk的链路集。则将Li调度到tk上所产生的干扰就体现为 Ski∪{Li}与 Ski在饱和度(即接纳新链路的能力)上的差异。对链路集LS与链路L，若 L S∪{L}为不可行集时，称链路集LS对于L饱和。显然，空集合的饱和度最小。任何新链路的加入都可能增大链路集的饱和度。但若新链路的干扰可通过SIC消除，则它的加入并不会改变链路集的饱和度。链路集LS的饱和度通过LS中的链路的抗干扰能力体现。

定义1 链路L∈LS的容忍度(tolerance margin)是指当LS的所有链路并发时，链路L所能容忍的最大干扰。

给定加权并发图，算法1给出了容忍度的计算过程。该容忍度是以下干扰值的较小者：①干扰L的任意一条相关链路的信号解码所需的最小干扰；②在所有相关链路的信号均被移除后，干扰L的信号解码所需的最小干扰。算法的 2)～3)行计算第②部分，而4)～10)行则计算了第①部分。链路的容忍度与可行性存在以下关系，其正确性不难证明。

定理2 链路集LS中的链路L可行，当且仅当L的容忍度大于0。

定理3 算法1的时间复杂度为O(|LS|2)，其中，|LS|为LS所含链路的数目。

证明 首先，第 2行需要遍历顶点 Li与 Lx(Lx∈LS)之间的边，其复杂度不超过O(|LS|)。其次，第 4)～10)行需要遍历所有形如 LiLy(Ly∈LS)的超顶点及其与 Lx(Lx∈LS)的边。每个超顶点的边数不超过O(|LS|)，而超顶点的数目不超过O(|LS|)。因而，复杂度不超过 O(|LS|2)，即算法的时间复杂度为O(|LS|2)。 证毕。

算法1 容忍度的计算

输入：SGW=(V,E,WV,WE)：加权并发图

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

输出： Li的容忍度

以图1中链路L1为例说明容忍度的计算。首先，移除相关链路的信号后，L1所受干扰为L4的信号与噪声。从而L1还能承受的干扰为M1=P11/11β-N0-P14。其次，考虑R1对相关链路信号的解码。对链路L2，链路L1与另一条相关链路L3的信号均为干扰，它的信号解码还能承受的干扰为M2=P12/β12-N0-P14-P13-P11。类似地，对链路L3，它的信号解码还能承受的干扰为M3=P13/β13-N0- P14-P11。最终，链路L1的容忍度为{M1, M2, M3}的最小值。

定义2 链路集LS的容忍度，记为 MLS，是指它在可行的前提下所能容忍的最大干扰。

集合的容忍度是其每条链路容忍度的最小值。链路集容忍度的计算方法如下：对链路集的每条链路应用算法 1，然后取所有结果中的最小值。对L∉LS，若有 MLS∪{L}≥0，则称LS对L可行。容忍度衡量了链路集的饱和度。空集合的容忍度为无穷大。新链路的加入，将可能导致容忍度的降低与饱和度的增加。最终，当容忍度降低到一个临界点，任何未调度链路的加入都将使得链路集为不可行，就称链路集达到饱和。类似地，对链路集的容忍度与可行性，存在如下关系。

定理4 链路集LS可行，当且仅当LS的容忍度大于0。

首次匹配策略的次优性在于其简单选择第一个可行的时间槽，而忽略了时间槽上所调度链路集的容忍度。考虑 2条链路 L1与 L2，假设P12/(N0+ P11) = β12。由于SIC可在L1的接收节点移除L2的信号，L1与L2可并发。但若它们并发，由于 M{L1,L2}= 0 ，任何其他链路都不能再调度到该时间槽上。从全网优化的角度看，将两者分配到不同时间槽，或许能得到更好的结果。因此，任意方式选择时间槽可能会增大最终所需的时间槽数目。

4.3 上下文感知调度

现在给出上下文感知的调度算法CONG，其过程如算法 2所示。首先将所有链路任意排序为l1, l2,… ,ln。在li调度之前，令Ni为已用时间槽的数目，Sij为在第j个时间槽上所调度的链路集。CONG按如下方式从l1开始依次处理每一条链路：①对每个计算的容忍度；②若Ni=0或对所有1 ≤ j≤ Ni，Sij对 li均不可行，则分配新时间槽以调度 li。否则，在所有可用时间槽中选择一个以调度 li。在处理完所有链路后，CONG返回总时间槽数目与每个时间槽上所调度的链路集。显然，所有链路集均为可行集。

算法2 上下文感知贪婪调度算法CONG

输入：SGW=(V,E,WV,WE)：加权并发图

输出：时间槽的数目M及调度S1,…,SM

定理5 算法2的时间复杂度不超过O(n3)，其中n为网络所含链路的数目。

证明 首先，对任意的链路集Sk，计算它的容忍度，时间开销不超过 O(|Sk|2)。同时，注意到而所有 Sk的链路总数不超过 O(n)。因此，第 4)～6)行的总时间开销不超过 O(n2)。其次，第 7)～10)行的时间开销为常数，而第 11)行所需的容忍度信息已被计算，选择过程的开销为 O(M)≤O(n)。总之，一次循环(第 4)～11)行)所需时间为 O(n2)。循环执行的次数不超过O(n)。从而，总的时间开销不超过 O(n3)。

证毕。

下面给出2种选择时间槽的策略。

最大残余优先（LRF, largest residue first）：在所有可用时间槽中，选择具有最大容忍度的第一个时间槽。对链路 li，选择第k个时间槽的条件：k是 TliΔ中的最小值，

最小减量优先（MDF, minimum decrease first）：在所有可用时间槽中，选择容忍度降低最小的第一个时间槽。对链路li，选择第k个时间槽的条件：k是ilTδ中的最小值，

2种策略的共同目标是将更多的链路调度到已选的时间槽中。一般地，容忍度越大，链路集接收新链路的能力越强。LRF的选择平衡了不同时间槽上的容忍度，避免在调度早期就导致大量时间槽上的链路集达到饱和。而MDF则更着眼于最小化当前链路被调度所产生的干扰。图3给出的例子展示了LRF与MDF的区别，假设调度il之前已使用 3个时间槽。由于LRF选择1t时间槽。然而，由于MDF选择3t时间槽。下面通过仿真实验考察 2种策略的性能。

图3 LRF与MDF区别的例子

5 性能评估

通过网络仿真器(NS 2, network simulator 2)[13]的仿真实验评价了近似方案的性能。表1总结了仿真过程中参数和协议的设置。评测性能指标为吞吐量，其中，平均吞吐量为总吞吐量(aggregate throughput)的平均，平均链路吞吐量为单条链路所获得的吞吐量的平均值。每一个数据点都是通过对多次运行结果取平均值获得。通过与首次匹配策略的比较来考察新调度机制的性能。2种新策略与首次匹配的实验结果分别用 LRF、MDF与 First-Fit表示。

NS 2并未提供对基于SINR模型的报文接收与SIC功能的支持。首先增加新的模块以支持累积干扰模型与SIC，详细描述可参考文献[5,7]。表1中的传输范围是指无其他并发传输时链路能正常通信的最大距离。若无特别说明，在每个时间槽的开始，每个源节点都依概率η发出一个报文。该概率对所有源节点均相同。

表1 仿真参数

首先在单跳情况下评估调度算法的性能。在150m×150m的区域内，随机分布100个节点并随机选取其中25个节点作为源节点。图4给出3种算法所得到的吞吐量。作为参考，利用数学规划可得到此时的最大吞吐量，用Optimal表示。LRF与MDF的表现很好。相比于First fit策略，LRF与MDF在吞吐量上的优势高达30%。此外，随着传输概率的增大，First-fit的吞吐量急剧下降。这是因为实验中链路以任意方式排序，当链路的数目很大时，每条链路的时间槽以First-fit方式任意选择，导致最终的调度性能很不理想。LRF与MDF的性能基本相当。但是，也必须看到，3种近似算法与优化值均有一定距离，设计更好的时间槽选择机制仍需进一步研究。

图4 单跳网络中平均吞吐量与传输概率的关系

为考察在较大规模的网络中SIC的效果，在一个500m×500m的区域内，均匀部署81个节点并随机选取其中30个节点作为源节点。对每个源节点，在其通信范围内随机选择一个节点作为目标节点。图5给出平均吞吐量与传输概率η之间的关系。考虑另一种流模式，令(x, y) (1≤x≤9, 1≤y≤9)表示不同位置的节点，考虑以下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 为取模运算，它返回v1除以v2的余数。每种流模式下均有9个不同的数据流。这些数据流可能需要多跳传输。不同流模式下，所需的转发链路数也不同。其中，P1所需链路数最小，X1次之，而X2所需最多。图6给出了3种流模式的吞吐量。

图5对应的场景中，随着η的增长，活跃链路的数目将逐渐增大。图 6对应的场景中，从 P1、X1到X2，总链路数目亦不断增多。随着网络包含越来越多的链路，可以预期在网络中将存在更多并发传输的机会。这些场景中，LRF与MDF展示出了明显优于First-fit的性能。

图5 81节点均匀分布的网络中平均链路吞吐量与传输概率的关系

图6 81节点均匀分布的网络中不同流模式时的平均链路吞吐量

最后，在一个 500m×500m的区域内随机方式部署100个节点。然后随机选取其中的30个节点作为源节点。对每个源节点，以随机方式选择目标节点。此时，一些节点对的传输需要多跳路由，所有活跃链路的总数在 30～48之间。图 7给出了在η= 0 .8时，平均吞吐量与链路数目的关系。与First-fit相比，LRF与MDF的吞吐量增益可达27%。

图7 100个节点随机分布的网络中平均链路吞吐量与链路数目的关系

6 结束语

本文研究了支持 SIC的静态无线网络中基于累积干扰模型的链路调度。首先给出加权并发图以描述网络干扰，并指出链路调度为NP-hard问题。然后，重点研究了贪婪调度算法。由于SIC的顺序检测特性与干扰的累积效应，如何准确衡量链路干扰是主要的研究挑战。现有的贪婪调度方法不能充分地理解与利用干扰信息，导致它们的性能不够理想。本文定义了容忍度以衡量链路集的饱和度，然后给出2个高效的策略为给定的链路选择最佳时间槽。在仿真实验中，2种策略的性能均优于常用的首次匹配策略。

[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.