对于网络中任意两个节点a、b(e_ab∈ E)和任意的正交信道集合c∈ {1, 2, …, |C|}, 定义一个变量 Xabc, 如果节点a与节点b之间通过信道c互相通信, 则 Xabc=1; 否则, Xabc=0。考虑到传输链路的对称性可以得到:

Xabc=Xbac1∀a, b∈N, ∀c∈{1, 2, …, |C}

对于网络中每个节点分配的信道, 定义一个变量 yac, 如果节点a的接口上分配有信道c, 则 yac=1; 否则, yac=0。可以得到 yac为:

0≤yac≤∑a, b∈N, eab=1Xabc2∀a, b∈N; ∀c∈{1, 2, …, |C}

Xabc≤yac≤1(3)∀a, b∈N; ∀c∈{1, 2, …, |C}

网络中每个节点都有固定的接口数, 每个节点连接的不同信道数量不能超过节点接口数, 即:

∑c=1Cyac≤I, a∈N4

当网络中某节点使用次数较多时, 同一条信道可能会被此节点多次使用, 但是当多条链路使用同一接口, 由于同一时间只有一条链路可以使用该接口, 会降低链路的有效容量。因此, 限制每个节点使用同一条信道的次数:

∑∀b∈Neab∈EXabc≤2(5)∀a, b∈N; c∈{1, 2, …, |C}

考虑网络中的链路容量以及干扰问题, 假设R⁰是IEEE802.11a标准的链路层数据速率, 定义 Rabc为节点a向节点b通过信道c发送数据的速率。考虑链路容量, 可以得出:

Rabc≤XabcR06∀a, b∈N; eab∈E; ∀c∈{1, 2, …, |C}

假设网络中的两条链路e_ij 、e_pq, 如果e_ij 任意端点在e_pq 的任意端点的干扰范围之内, 则e_ij 与e_pq 互为干扰链路。对于网络中一条链路e_ab, 定义一个集合L_ab⊂E, L_ab 代表链路ab相互干扰边的集合, e_ba∈ L_ab 。考虑网络中的干扰, 可以得到^[14]:

RabcR0+∑m, n, mn∈LabRmncR0≤1(7)∀a, b, m, n∈N; emn; eab∈E; ∀c∈{1, 2, …, |C}

式中:m、n为网络中任意两节点; Rabc/R0表示从节点a通过信道c向节点b发送数据包的时间占用比例。

考虑网络中存在的传输流, 假定源节点s和目的节点d, r_sd表示从节点s向节点d发送数据包的传输速率。定义一个传输流变量 fab, csd, 当节点s向节点d发送传输流时, 经过链路e_ab 时使用信道c, 则 fab, csd=1; 否则, fab, csd=0。

当节点s向节点d发送数据包时, 经过链路e_ab, 如果a, b之间的链路在多条信道上传输, 不同信道的时延不同, 可能会导致数据包到达的顺序混乱。为了避免这一现象, 一条传输流在两个节点之间通过时, 只在一条信道上进行传输, 即:

∑c=1Cfab, csd≤1, ∀s, d, a, b∈N; eab∈E8

定义变量 φabc来表示当网络中所有的传输流通过信道c在节点a与节点b之间的链路上进行传输时, 在节点a, b间通过信道c的全部传输流的总速率:

φabc=∑s, d∈Nfab, csdrsd9∀a, b, s, d∈N; c∈1, 2, …, C; eab∈E

在实际网络中, 某条链路传输流的总速率不能超过该链路的标准链路层速率一定比例, 将这个比例称为链路占用率:

φabc≤μRabc10∀a, b∈N; eab∈E; ∀c∈{1, 2, …, |C}

式中: μ为不大于1的正参数, 为网络中最大链路占用率。

当一条链路的链路占用率过大时, 会出现时延增加, 丢包率变大的情况。为保证网络性能, 链路占用率不能太大, 考虑网络中的负载均衡, 将占用率大的链路的传输流分配到占用率较小的链路, 提出目标函数最小化μ 。

当网络中存在传输流时, 要确保传输流是可行流, 即, 对于节点 s、d、a,应有:

∑b∈N, eab∈E∑c=1Cfab, csdrsd-∑n∈N, eab∈E∑c=1Cfba, csdrsd=rsd, s=a-rsd, d=a0, 其他11

另外, 当节点 s向节点d发送数据包时, 所选路径经过的链路数越多, 产生的干扰就越大, 对网络性能的影响越严重。所以在进行路由度量时, 应保证传输流在一定跳数内到达目的节点, 应有:

∑a, b∈N, eab∈E∑c=1Cfab, csd≤εhsd, ∀s, d∈N12

式中:ε 为一个不小于1的实数; h_sd 为从节点s到节点d的最小跳数; ε h_sd在数据包传输时, 所能接受的最大跳数。

由式(7)可得:

Rabc+∑m, n, mn∈LabRmnc≤R013∀a, b, m, n∈N; emn, eab∈E; ∀c∈{1, 2, …, |C}

由式(9)(10)(13)可得:

∑s, d∈Nfab, csdrsd+∑s, d∈N; m, n∈Labfmn, csdrsd≤μR014∀a, b, m, n, s, d∈N; ∀emn, eab∈E

由式(6)(9)(10)得:

∑s, d∈Nfab, csdrsd≤XabcR015∀a, b, s, d∈N; ∀eab∈E; ∀c∈{1, 2, …, |C}

由式(1)~(15), 得到混合整数线性规划问题:

minimizeX, y, Ca, f, μ μXabc=Xbac0≤yac≤∑a, b∈N; eab=1XabcXabc≤yac≤1∑c=1Cyac≤I∑∀b∈N; eab∈EXabc≤2∑c=1Cfab, csd≤1∑b∈N, eab∈E∑c=1Cfab, csdrsd-∑n∈N, eab∈E∑c=1Cfba, csdrsd= rsd, s=a-rsd, d=a0, 其他∑a, b∈N, eab∈E∑c=1Cfab, csd≤εhsd∑s, d∈Nfab, csdrsd+∑s, d∈N; m, n∈Labfmn, csdrsd≤μR0∑s, d∈Nfab, csdrsd≤XabcR016

式中：

Xabc, fab, csdyac∈{0, 1}; rsd, hsd, ε, μ≥0; ∀a, b, m, n, s, d∈N; ∀eab, emn∈E; ∀c∈1, 2, …, C。

令W代表源和目的节点对的数目, |N|、|E|和|C|分别是集合N、E和C的基数。由式(16)可以得出, 混合整数线性规划有 |E|C|(1+|W|)+|N|C|个整数变量以及1个实数变量, 同时有 |E|C+W|N|个等式以及 |N|×(|C|+1)+W|E|+1)+3|E|C|个不等式限制条件。

文献^[13]所提贪婪算法只考虑初始值的可行性, 没有考虑迭代时的收敛速度。考虑规划模型达到优化网络公平性, 提出考虑网络公平性的贪婪算法, 同时为尽可能多的链路分配信道, 形成一个初始值。

贪婪算法首先将节点按照连接边数从小到大排序, 然后先为连接边数小的节点分配链路, 尽可能保证所有节点的连通性。

将每个节点的链路按照干扰链路数的多少进行优先级排序, 干扰链路少的优先级高, 然后按照优先级从高到低的顺序进行信道分配。

对于每条信道, 首先考虑此信道是否对此链路可用, 如果有多信道可用, 则考虑各信道被已分配干扰链路占用的次数, 再选择被占用次数最少的信道分配给该链路。

贪婪算法形成的初始值保证了网络的连通性, 将其代入ILS算法时, 可以使ILS算法得到一个可行的初始值, 同时可以更快地收敛, 达到降低算法计算量和减少计算时间的目的。

ILS算法设定一个最大迭代次数, 以防止算法的运行量过大。将贪婪算法获得的初始值代入ILS算法, 在每次迭代过程中, 随机选择两个节点p、q, 除了p、q两个节点使用的链路外, 其他链路都被分配一条初始信道。整数变量 fab, csd的限制放宽为: 0≤fab, csd≤1, 获得的 Xabc结果作为下一次迭代的代入值。在整个迭代过程结束后, 处理获得的 fab, csd值, 对于每一对源和目的节点对, 选取下一跳中 fab, csd值最大的节点使其值等于1。在所有的源和目的节点对都处理完成后, 将所有值不为1的 fab, csd都归0, 获得最终的分配结果。

本文采用以下指标对算法进行评价。

(1)收敛次数:迭代过程中, 目标函数值达到最优值的最小迭代次数。

(2)最大链路占用率:同一时间一条逻辑链路及其干扰范围内的链路传输速率与该链路容量的比值, 即式(10)中的μ 。

(3)网络吞吐量:单位时间内网络中所有目的节点成功接收的比特数, 其表达式如下:

T=∑i=1NfJi(tend-tstart)·102417

式中:T为网络吞吐量; N_f 为网络中传输流的个数; J_i 为传输流i的接收节点成功接收到数据包的比特数; t_end为接收最后一个数据包的时间; t_start为发送第一个数据包的时间。

(4)平均端到端时延:网络中所有数据包从源到目的节点的平均传输时间。

D=∑j=1NrDj/Nr18

式中:D为平均端到端时延; D_j为数据包j的端到端时延; N_r为目的节点成功接收数据包的数目。

(5)网络平均丢包率:网络中所有没有成功传输的数据包数量与发送数据包总数量比值。

L=NlossNtotal19

式中: L为网络平均丢包率; N_loss为丢失数据包的总量; N_total为发送数据包的总量。

(6)网络公平性:若一个网络结构在相似网络负载以及传输情况下各节点可以获得接近的网络性能, 则这个网络具有高网络公平性。使用Jain等^[15]提出的网络公平性指标:

ΨPDR= ∑s, d∈N, rsd≠0P(s, d)2W∑s, d∈N, rsd≠0P(s, d)220

式中:Ψ _PDR为网络公平性; P为数据包递交率(Packet delivery ratio, PDR), 是一个目的节点接收到的数据包与其对应源节点发送数据包的数量的比值; W为网络中传输流的数量。

改变网络中的流数, 将文献^[9]算法(本文将其命名为UILS(Used iterated local search)算法), 观察在传输流数量不同的情况下, ILSG算法与UILS算法的收敛次数, 所得仿真结果如表1所示。从表1可以看出, 由于所选择的源和目的节点对的不同, 两种算法的收敛次数呈现不规律的变化, 但是ILSG算法的收敛速度始终优于UILS算法。

表1

Table 1

表1(Table 1)

表1 收敛次数比较 Table 1 Comparison of convergence times 传输流数量 ILSG平均收敛次数 UILS平均收敛次数 10 3 7 15 10 16 20 3 7 25 6 9 30 3 5

表1 收敛次数比较 Table 1 Comparison of convergence times

考虑ILS算法初始值链路占用率大, 如果传输速率过大, 会超出链路承受范围。选取较小传输速率, 保持网络中传输流数量为30, 源和目的节点对一致, 比较ILSG算法和ILS算法的收敛情况, 仿真结果如图2所示。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 两种算法的收敛情况Fig.2 Comparison of convergence of two algorithm

从图2可以看出, 两种算法都在不断向最优解方向接近, 但是ILSG算法的收敛明显比ILS算法要快, 可以降低算法计算次数, 从而降低算法复杂度。

固定节点数量为30, 在不同传输流个数下对算法网络性能进行比较。首先使用贪婪算法进行初始信道分配, 基于信道分配结果使用文中优化模型式(16)进行路由度量, 文中表示为贪婪算法; 然后利用分支定界法^[16]求得算法优化理想值。将ILSG算法与贪婪算法以及理想值进行仿真比较。仿真结果如图3所示。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 链路占用率比较Fig.3 Comparison of link occupancy rate

从图3可以看出, ILSG算法链路占用率低于贪婪算法, 证明联合优化可以更好地利用网络资源, 提升网络性能。混合整数线性规划的算法复杂度取决于所含整数变量^[16], ILSG算法使用更低的算法复杂度解决规划模型, 同时链路占用率与理想值接近, 证明了ILSG算法的可行性。

固定节点数量为30, 在不同传输流个数下对算法网络性能进行比较, 仿真结果如图4所示。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 网络性能比较Fig.4 Comparison of performance of network

从图4可以看出, 在网络中传输流数量在一定范围内增加时, 网络平均吞吐量随传输流数量增加而增大。但是当网络中传输流数量足够大时, 吞吐量会变小, 这是因为当网络中传输流数量过大时, 会造成网络拥塞, 丢包率变大, 网络中的时延越来越大。从图4可以看出, 当网络中传输流数量较少时, 两种算法的网络性能相差不大, 但是随着传输流数的增加, ILSG算法网络性能要优于贪婪算法, 因为ILSG算法模型对信道与路由进行联合优化, 考虑信道分配与路由间的相互影响, 使网络资源得到充分的利用, 优化了网络性能。

改变网络中的流数, 比较两种算法分配结果的网络公平性, 所得结果如表2所示。从表2可以看出, 当网络中传输流数量较少时, 每种结构都能以高公平性传输数据包, 这是因为网络中传输流数量较少时, 每条传输流都以较高的递交率进行传递。但是当网络中传输流增多时, 网络公平性下降, 可以看出ILSG算法公平性要优于贪婪算法。因为当网络中传输流数量很多时, 网络中传输流开始呈现不同的递交率, 此时考虑信道与路由联合优化可以更好地利用网络资源, 提高网络性能。

表2

Table 2

表2(Table 2)

表2 网络公平性比较 Table 2 Comparison of network fairness 传输流数量 ILSG 贪婪算法 10 1 0.999 15 0.999 0.993 20 0.998 0.990 25 0.967 0.955 30 0.906 0.876

表2 网络公平性比较 Table 2 Comparison of network fairness