0 概述

近年来, 无线传感器网络(Wireless Sensor Networks, WSN)在农业、交通运输、环境监测等领域得到广泛应用。在WSN中有规律或随机地部署着大量具有计算、存储、信息传输等功能的节点, 且节点以单跳或多跳的方式将实时采集到的信息发回到基站。但是, 这些节点由电池供电且一般会布置在人迹罕至的地带, 因此, 在实际应用中需要提高节点的能量利用率以及均衡度。拓扑控制技术能够有效延长传感器节点的生命周期, 均衡各节点的能量消耗^[1-3], 因此, 其逐渐成为该领域的研究热点之一。

目前, 多种WSN拓扑控制算法相继被提出^[4-5]。文献[6]设计一种分布式能耗均衡拓扑控制算法, 其能提高附近节点的平均剩余能量, 然后选择剩余能量较多的节点作为自己的邻居节点, 进而提高节点的能耗均衡度。文献[7]提出基于博弈论的分布式最优响应拓扑控制算法MIA及其改进算法DIA, 从而确保所构建拓扑的唯一性。文献[8]提出一种自适应的协同拓扑控制算法CTCA, 其将网络寿命最大化问题映射为一种序数势博弈问题, 主效用函数用来提高反向链路集中节点的最短寿命, 次函数用于提高自身寿命。文献[9]提出一种WSN能耗均衡的自适应拓扑博弈算法ATCG, 其根据节点的寿命调整自身发射功率, 从而延长整个网络的生存时间。上述算法均能较好地控制拓扑, 但并未考虑网络基站节点的位置, 数据传输压力会集中在距离基站较近的节点上, 造成该节点“生命”过早结束。因此, 节点的位置也是拓扑控制中必须考虑的因素之一。

随着网络的持续运行, 节点的能量分布将变得不均匀^[10], 接近基站的传感器节点由于传输数据量较大, 能量消耗过快, 其“生命”将提前结束。本文综合考虑节点的剩余能量、发射功率以及节点到基站的传输距离, 在保证网络整体连通度和覆盖度的基础上, 提出一种基于势博弈的WSN分布式拓扑控制算法BLTC。

1 基于势博弈的拓扑控制模型 1.1 WSN模型

根据图论及相关理论^[11-12], 本文假设网络中的节点均为同类型的传感器节点, 随机部署在待监测区域, 通过拓扑控制算法来构造WSN拓扑结构, 以延长网络生命周期。定义WSN拓扑为G<N, V, P>, 其中, N={1, 2, …, n}为所有网络节点的集合, V为任意2个节点之间通信链路的集合, 其是一个n维矩阵, 2个节点之间若连通, 则V的元素值为1, 不连通则为0, P为节点发射功率的集合。

1.2 博弈论及相关理论

策略型博弈为一个三元组^[13] < N, (S_i)_i∈N, (u_i)_i∈N>, 其中, N={1, 2, …, n}是参与者集合, 其由参与者1, 2, …, n组成, S₁, S₂, …, S_n分别是参与者1, 2, …, n的策略集, 通常可以用s=(s_i, s_－i)∈S来表示一个策略组合, s_i表示参与者i的策略, s_－i表示剩下n－1个节点的策略。u_i:S₁×S₂×…×S_n→R(i=1, 2, …, n)是一组映射, 称为效用函数或收益函数, u_i(s_i, s_－i):S→R为参与者i选择(s_i, s_－i)策略时的收益。

纳什均衡是博弈论中的一个核心概念^[14], 其表示在一个事件中, 所有参与者都有自己最好的方法, 无论别人采取何种策略, 只要他们不改变自己的方法, 当事人都会让对自己最好的策略不改变, 这时, 每个人的策略组合便为纳什均衡。

定义1(纳什均衡)   给定一个策略型博弈Γ= < N, S_i, u_i>及其策略组s^*=(s₁^*, s₂^*, …, s_n^*), 若有:

$ {u_i}\left( {s_i^*, s_{ - i}^*} \right) \ge {u_i}({s_i}, s_{ - i}^*) $

(1)

则对于所有s_i∈S_i, i=1, 2, …, n, s^*是Γ的一个纯策略纳什均衡。

一个博弈中可能有一个、多个均衡, 或者不存在均衡^[15]。为保证存在纳什均衡, 文献[16]提出势博弈的概念, 并证明在势博弈中至少存在一个纳什均衡。

定义2 (序数势博弈)   对于策略型博弈Γ= < N, S_i, u_i>, 如果存在一个函数V:S→R, ∀i∈N, ∀s_－i∈S_－i, 对于∀a_i, b_i∈S_i有:

$ \begin{array}{l} V\left( {{a_i}, {s_{ - i}}} \right) - V\left( {{b_i}, {s_{ - i}}} \right) > 0 \Leftrightarrow \\ {u_i}\left( {{a_i}, {s_{ - i}}} \right) - {u_i}\left( {{b_i}, {s_{ - i}}} \right) > 0 \end{array} $

则称博弈Γ为序数势博弈, 函数V是博弈Γ对应的序数势函数。

定理1   若策略型势博弈Γ= < N, S_i, u_i>为序数势博弈, 函数V是博弈Γ对应的序数势函数, 并且存在一个能够使V最大化的策略组合s∈S, 则该策略组合可以作为博弈Γ的纳什均衡^[17]。

1.3 拓扑控制博弈模型建立

本文将无线传感器网络控制定义为策略型博弈中的势博弈Γ= < N, S_i, u_i>。其中, N={1, 2, …, n}表示网络中n个节点的集合, S=S₁×S₂×…×S_n是策略集合S_i的笛卡尔积, S_i={0, p_i¹, …, p_i^max}为节点i的可选择功率集合, u_i为节点i的效用函数。

在拓扑控制模型的建立过程中, 确定效用函数是一个重要步骤。本文结合节点数据传输过程中的特性, 设计能够较好反映网络状况的效用函数u_i。对于节点i, 有:

$ \begin{array}{l} {u_i}\left( {{p_i}, {p_{ - i}}} \right) = {c_i}\left( {{p_i}, {p_{ - i}}} \right)b{R_{ij}}{R_j} - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{p_i}\left( {{x_1}\cdot\frac{{{E_o}\left( i \right)}}{{{E_r}\left( i \right)}} + {x_2}\cdot\frac{{{D_{\max }}}}{{D(i)}}} \right) \end{array} $

(2)

其中, x₁、x₂为权重因子, 且都设为正数, c_i(p_i, p_－i)表示节点的连通性, 当其值为1时网络连通, 其值为0时网络不连通, b为数据成功发送后的奖励, R_ij为节点i成功发送到下一节点的成功率, R_j为节点i下一跳节点发送到基站的成功率, p_i为节点i的发射功率, E_o(i)为节点i的初始能量, E_r(i)为节点i的剩余能量, D_max为整个网络中信息需要传递到基站的最远距离, D(i)为节点i信息传输到基站的距离。

从${{x_1}\cdot\frac{{{E_o}\left( i \right)}}{{{E_r}\left( i \right)}}}$可以看出, 当节点i的能量降低之后, 其会尽量选取发射功率较小的策略进行工作; 从${{x_2}\cdot\frac{{{D_{\max }}}}{{D(i)}}}$可以看出, 距离基站越近, 该值越大, 因此, 节点也会倾向于选择发射功率较小的策略进行工作。

1.4 理论证明

定理2   设博弈Γ=<N, S_i, u_i>是一个序数势博弈, 定义其序数势函数为:

$ \begin{array}{l} V\left( {{p_i}, {p_{ - i}}} \right) = \sum\limits_{i \in N} {{c_i}\left( {{p_i}, {p_{ - i}}} \right)\cdot b{R_{ij}}{R_j} - } \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{p_i}\left( {{x_1}\frac{{{E_o}\left( i \right)}}{{{E_r}\left( i \right)}} + {x_2}\frac{{{D_{\max }}}}{{D(i)}}} \right) \end{array} $

(3)

证明   节点选择不同发射功率p_i、q_i时的收益差值为:

$ \begin{array}{l} \Delta {u_i} = {u_i}\left( {{p_i}, {p_{ - i}}} \right) - {u_i}\left( {{q_i}, {p_{ - i}}} \right) = \\ \;\;\;\;\;\;\;\;\;\;\left[ {{c_i}\left( {{p_i}, {p_{ - i}}} \right) - {c_i}\left( {{q_i}, {p_{ - i}}} \right)} \right]b{R_{ij}}{R_j} - \\ \;\;\;\;\;\;\;\;\;\;\left( {{p_i} - {q_i}} \right)\left( {{x_1}\frac{{{E_o}\left( i \right)}}{{{E_r}\left( i \right)}} + {x_2}\frac{{{D_{\max }}}}{{D(i)}}} \right) \end{array} $

(4)

同理, 有:

$ \begin{array}{l} \Delta V = V\left( {{p_i}, {p_{ - i}}} \right) - V\left( {{q_i}, {p_{ - i}}} \right) = \\ \;\;\;\;\;\;\;\;\;\left[ {{c_i}\left( {{p_i}, {p_{ - i}}} \right) - {c_i}\left( {{q_i}, {p_{ - i}}} \right)} \right]b{R_{ij}}{R_j} - \\ \;\;\;\;\;\;\;\;\;\left( {{p_i} - {q_i}} \right)\cdot\left( {{x_1}\frac{{{E_o}\left( i \right)}}{{{E_r}\left( i \right)}} + {x_2}\frac{{{D_{\max }}}}{{D(i)}}} \right) + \\ \;\;\;\;\;\;\;\;\;\sum\limits_{j \in N, j \ne i} {{c_j}\left( {{p_i}, {p_{ - i}}} \right) - {c_j}\left( {{q_i}, {p_{ - i}}} \right) - } \\ \;\;\;\;\;\;\;\;\;\left( {{p_j} - {q_j}} \right)\cdot\left( {{x_1}\frac{{{E_o}\left( i \right)}}{{{E_r}\left( i \right)}} + {x_2}\frac{{{D_{\max }}}}{{D(i)}}} \right) = \\ \;\;\;\;\;\;\;\;\;\Delta {u_i} + \Delta {V_1} \end{array} $

(5)

因此, Δu_i与ΔV可以分为以下4种情况进行讨论:

1) 当p_i>q_i, c_i(p_i, p_－i)=c_i(q_i, p_－i)时, Δu_i < 0, ΔV < 0, 故两者同号, 表示此博弈为序数势博弈。

2) 当p_i < q_i, c_i(p_i, p_－i)=c_i(q_i, p_－i)时, Δu_i>0, ΔV>0, 故两者同号, 表示此博弈为序数势博弈。

3) 当p_i < q_i, c_i(p_i, p_－i) < c_i(q_i, p_－i)时, Δu_i=ΔV, 故两者同号, 表示此博弈为序数势博弈。

4) 当p_i>q_i, c_i(p_i, p_－i)>c_i(q_i, p_－i)时, Δu_i=ΔV, 故两者同号, 表示此博弈为序数势博弈。

由此可知, sgn(Δu_i)=sgn(ΔV), 博弈Γ= < N, S_i, u_i>是一个序数势博弈, 至少存在一个纳什均衡。

2 WSN非均匀拓扑控制算法

在本文系统中, 整个网络的所有节点以最大发射功率构建初始网络, 然后运行BLTC算法, 各节点之间进行博弈, 不断地降低发射功率, 直至达到纳什均衡。BLTC算法主要包含3个阶段:初始化阶段, 博弈阶段, 拓扑维护阶段。

2.1 初始化阶段

每个节点以最大发射功率p_i^max进行初始化, 然后广播其节点ID、剩余能量以及到基站的距离, 并确定可覆盖邻居集。每个节点还需计算可到达邻居集的发射功率, 构成策略集S_i={0, p_i¹, p_i², …, p_i^max}, 并将其反馈至基站。

2.2 博弈阶段

网络博弈阶段主要依靠各节点的剩余能量以及位置信息, 动态调整拓扑结构, 均衡能量消耗。网络中每个节点都根据ID顺序进行博弈, 然后调整自身的发射功率。每轮只有一个节点进行博弈, 确定发射功率后进行广播, 通知其余节点。若降低自身的发射功率能够比当前获得更高的收益, 则选择此策略并更新策略集, 否则保持原状态不变。经过反复的博弈及更新, 最终达到博弈的均衡点。BLTC算法伪代码如下:

算法1    BLTC算法

1.BLTC(G(V, E))

2.P_i=p_i^h   ∀i∈N

3.for all i, h=0

4.p_i =p_max

5.P={P₁, P₂, …, P_N}

6.do

7.h=h+1

8.p=adjust(p)

9.end for

10.while (P达到最优)

2.3 拓扑维护阶段

经过反复迭代之后, 会出现能量消耗过多的节点, 此时需要对拓扑结构进行维护^[18]。本文采取规定时间轮数与规定失效节点个数相结合的方法, 并执行拓扑生成算法, 以更好地均衡能量消耗、延长节点生命周期。

3 仿真结果与分析

本文采用Matlab作为仿真软件, 分析算法在节点能量方差、节点平均发射功率、死亡10%节点时的迭代轮数(简称轮数)以及死亡节点分布方面的性能。比较算法包括BLTC算法、基于博弈论的分布式最佳响应算法DIA^[7]、虚拟博弈能量均衡算法VGEB^[16]。仿真参数设置如表 1所示。

本文将50个传感器节点随机部署在500 m×500 m的环境中, 基站位于(0, 0)处。3种算法构建的拓扑结构分别如图 1(a)、图 1(b)、图 1(c)所示。可以看出, DIA算法生成的拓扑结构中含有很多网络负载较重的节点, 因此, VGEB算法和BLTC算法比DIA算法具有更好的稳定性与健壮性。BLTC算法能够使距离基站较近位置的传感器节点拥有较高的节点度、较小的覆盖面积, 从而降低这些节点的负载, 达到均衡网络能耗的目的。

图 2~图 4所示分别为节点平均发射功率、节点平均度以及轮数的变化曲线。从图 2可以看出, 在固定区域内, 随着节点数目的增多, 节点平均发射功率降低。BLTC算法在保证网络连通性的基础上具有更低的平均发射功率。从图 3可以看出, VGEB算法中节点平均度随着节点数目的增多而增大, DIA算法和BLTC算法中的节点平均度分别稳定在2.2和2.4左右, BLTC算法既能保证网络的连通性, 又能使节点以较低的功率工作。从图 4可以看出, DIA算法由于各节点传输任务重、负载大, 较早地出现死亡节点, 而BLTC算法和VGEB算法拓扑结构存在冗余, 策略的选择较为丰富, 不会过多消耗能量, 因此, 能有效避免节点过早死亡的现象。

图 5所示为网络节点剩余能量方差的变化曲线。从图 5可以看出, 随着时间的变化, 3种算法所构建拓扑结构中的节点剩余能量方差都会不同程度地增大, 但BLTC算法中节点的能量方差更小, 说明其网络节点的能量消耗更加均衡, 而DIA算法和VGEB算法中的节点能量方差较高, 说明其基站附近的节点能量消耗过快。图 6所示为3种算法的死亡节点分布情况, 从图 6可以看出, DIA算法和VGEB算法死亡10%节点时节点分布较集中, 前者集中在基站附近, 后者集中在某一条通信链路中。与上述两者相反, BLTC算法生成的网络中死亡节点的分布较为分散, 即该网络具有更好的鲁棒性^[19], 在死亡节点出现时, 不会轻易崩溃, 避免了网络“空洞”现象的发生^[20]。

4 结束语

本文针对无线传感器网络节点能量消耗不均衡的问题, 构建一种考虑节点剩余能量、信息传输成功率以及节点到基站之间距离的博弈模型, 并提出基于势博弈的非均匀拓扑控制算法BLTC。仿真结果表明, 该算法在保证网络连通性的同时, 能够有效均衡节点的能量消耗, 提高网络的鲁棒性并延长节点的生命周期。