解决相邻信道传输之间的干扰引起的约束问题, 利用联合信道分配和路由器接口分配, 将该问题看作是一种跨层网络效用最大化问题。在一个多信道无线Mesh网络中, 两个逻辑链路 (m, n), (m, p)∈L被定义为相互干扰, 必须同时满足如下条件:

(1)逻辑链路工作在同一信道, 即 xTmnxmp=1。

(2)一个信道的发送/接收接口是在其他信道的发送/接收接口的干涉范围内。

通过建模, 博弈了理论有效的改善路由协议性能。两个参与者的初始状态是最小化参与者和最大化参与者。定义博弈的每一个参与者和收益函数, 量化最小参与者的结果; 最小化参与者选择最小化函数, 最大化参与者选择最大化函数。在使用博弈模型中, 两个参与者是同样的。所有的路由器聚集到一起形成一个参与者, 是路由器参与者的集合; 另一个参与者是链路的集合, 是网络参与者。路由器参与者集合的博弈移动是执行路由协议。网络参与者博弈移动是改变网络拓扑。极大极小策略搜索博弈树找到极大极小路径; 极大极小值(极大极小结果)是应用到路径上的代价函数。极大极小值是在博弈的约束内, 如果路由器已经被优化, 那么, 在网络内无论发生什么, 路由器确保不会低于极小极大值。

不可转移收益合作博弈模型包括4个基本要素:局中人、结果集合、特征函数、以及收益函数。其中, 局中人(参与者)是博弈过程中的决策主体, 结果集是 X,将 N的每个非空子集 S(即一合作)赋一个集合 V(S)⊆X的特征函数 V。收益函数是局中人从各种策略中能够获取的收益。其中, N={1, 2, …, n}为全部博弈局中人的集合, S= S1×S2×…×Sn为所有参与者的策略的集合, × 为笛卡尔乘积。参与者i的收益是一个测量函数, 用u_i来表示。 U表示所有局中人获得的收益集合, 其中 U={u1, u2, …, un}。不可转移收益模型是一种静态的博弈模型, 在这个模型中, 一些参与者合作达到高的收益率。本文采用极大极小合作纳什均衡, 目标是最大化通信线路的收益, 分析极大极小合作纳什均衡的存在, 证明极大极小合作纳什均衡的必要条件。仿真结果显示, 根据合作收益得到的多跳链路数据速率, 极大极小合作纳什均衡优于合作纳什均衡方案和纳什均衡方案。

联合簇间公平路由与信道分配对随机博弈网络定义如下:

SGN=(N, T, P, F, π, λ, R, U, M0)

式中： N={1, 2, …, n}为参与者的集合; T=TS⋃T1⋃T2⋃…⋃Tn为转换的集合, 其中 Tk, k∈N为参与者 k的行为转换的集合, TS为系统行为剩余转换的集合; P=PS⋃P1⋃P2⋃…⋃Pn为地点的有限集合, Pk为参与者 k采取行为的地点的集合, PS为显示系统状态的剩余地点的集合; Ti∈[0, 1], i∈1, 2, …, n为一个路由策略, 代表参与者i选择转换的概率, 定义 ·x={y|(y, x)∈F}为 x的前集, x·={y|(x, y)∈F}为 x的后集; R(1, 2, …, N)为每个转换的收益函数, 其中 i∈(-∞, +∞)对于 i∈N; U为参与者收益函数; M0为初始市场; 参与者 i的满意度为 Ti/Ri;参与者平均收益率为 ∑iU_i/ ∑iR_i。

每个参与者采用一个统一的随机分布策略, 比如以0.5 的概率选择一个信道将本文采用的信道分配与随机分配信道相比较, 5个参与者的节点的满意度明显高于随机分配。

剩余能量越小, 成为簇头的概率越小:

fi=EiEi0(1)

式中: fi为节点 i当前的剩余能量, 取值范围为[0, 1]; Ei为节点 i在初始状态时所具有的能量; Ei0为剩余能量因子。

令簇头间的距离为最佳距离, 就可以使得周围节点密度较大的节点更有可能成为簇头节点。

Leach协议不考虑节点是否曾经担任过簇头, 对节点的任务分配极为不公平。对比分析节点的状态函数, 增加节点的节点需求带宽等参数, 构建节点的状态描述模型:定义 ci, j为节点 i在某一时刻 j的贡献值衡量函数, Δc为不同的贡献变化值, 而如何选择最终的簇头节点, 就需要通过博弈论来解决问题。

cij=∑k=0j-1cik+Δc(2)

Ui=LwMpici, j+LwMpiΔc-sib∑j=1Nsjτ, i∈N(3)

式中: b∈(0, 1]为 Ui函数中可调的参数, 表示节点的带宽需求的满意程度, Ui为效用函数; Lw为节点在带宽w下传输数据帧(不包含控制信息)的长度为L; 节点i在发送功率p下传输数据帧的长度为M; 0≤ s₁≤ s₂≤ …≤ s, S_i={0, s_1, s₂, …, s}为参与者i的策略空间。

对于任何两个节点 m, n∈N, 存在一条逻辑链路 (m, n)∈L, 定义一个 C×1的信道分配向量 Xmn, 如果节点 m与n在第i条频道进行通信, 那么向量 Xmn中的第 i个元素就被设置为1; 否则, 将被设置为0。例如, 假设 C=5, 节点m与n在第2条频道上进行通信, 则 Xmn=[01000]T。

为了建立逻辑链路 (m, n)∈L,路由器节点 m与 n应该分配通用的信道, 即:

X_mn=X_nm, ∀ m, n∈ N, (m, n)∈ L (4)

l^TX_mn=1, ∀ m, n∈ N, (m, n)∈ L (5)

式中:l表示一个C× 1的信道分配向量, 其所有的向量元素均为1。考虑两个逻辑链路(m, n), (m, p)∈ L, 有如下公式:

XmnTX_mp= 1, 逻辑链路m, n和m, p 使用同一个链路0, 其他(6)

对于任何两个节点 m, n∈N,存在一条逻辑链路 m, n∈L, 定义一个 I×1的接口分配向量 Ymn, 如果节点 m的第 i个接口与节点 n进行通信, 那么向量 Ymn中的第 i个元素就被设置为1; 否则, 将被设置为0。例如, 假设 I=3, 节点m使用其第1个接口与节点 n进行通信, 则 Ymn=[100]T。

为了建立逻辑链路(m, n)∈ L, 路由器节点m与n应该使用它们的一个接口。需要特别注意的是, Y_mn≠ Y_nm。然而, 其仍然需要满足:

l^TY_mn=1, ∀ m, n∈ N, (m, n)∈ L(7)

如果两个邻居逻辑链路 m, n, (m, p)∈ L共享节点m的一个接口(即, YTmnY_mp=1), 那么它们将被分配同一个信道(即, XTmnX_mp=1)。与之相反, 如果他们没有共享节点的同一个接口(即, YTmnY_mp=0), 那么它们将被分配不同的信道(即, XmnTX_mp=0)。在本文中假设C≥ I, 可以对信道分配和接口分配向量之间的关系进行建模, 具体描述如下:

XmnTX_mp= YmnTY_mp (8)

∀ m, n, p∈ N; (m, n), (m, p)∈ L

信道和接口联合分配模型可以表示为< X, Y> , 在模型由信道分配向量X_mn和接口分配向量Y_mn共同决定了所有逻辑链路(m, n)∈ L的分配。

为Mesh传感器网络构造收益函数, 通过并行迭代的方式获得网络信道分配的纳什均衡策略, 使所有节点的收益函数达到最优化, 节点i的收益函数U_i=M是节点i占用带宽进行直接传输所获得的吞吐量与节点i所获得的吞吐量之和除以节点i对所占用的协作带宽w_i的支付。

对于联合合作博弈的模型, 由于寻求模型(3)最优解的问题是一个NP难题, 本文尝试用贪婪算法寻求近似最优解。

贪婪算法:设I表示当前带宽需求低的节点(参与者)构成的集合, 若当前最大收益为U_i(j)=max_{k∈ N, l∈ j}r_l(k)则说明参与者i的带宽需求高, 则将参与者i放入表示带宽需求高的节点构成的集合j。

每个Mesh节点根据策略S_i来选择效用U_s, 如果效用函数提高, 则博弈过程再次进入循环。同时所有节点依次进行次操作从而达到纳什均衡。本文博弈基本算法步骤如下:

(1)初始化, 为N个Mesh节点分配信道, 所有节点的策略组合记为S⁰。

(2)迭代过程, 节点按照接入网络的顺序依次进行博弈, 依次选择使得效用函数最大的策略, 更新所有节点的策略组合为S^* 。

(3)终止过程, 重复迭代过程, 直至算法收敛。