近年来，物联网由于自组织、低成本等优势，越来越受到普及[1]，被广泛应用于智能交通、智慧家庭和数字医疗等场合[2]．物联网大部分覆盖采用随机部署的方式，这会产生大量的节点冗余．而在节点数目限制的条件下，随机部署难以满足目标区域的覆盖，通常会存在一定的覆盖间隙．优化传感器部署的位置可以减少覆盖重叠，满足最大区域覆盖，因此可以让传感器节点移动，寻找最佳部署位置，减少重叠覆盖，提升覆盖率．而传感器节点的移动会引起大量的能量消耗，在考虑能耗的情况下，为传感器节点制定合理的移动策略是解决覆盖优化问题的关键．在能耗和覆盖率制衡算法方面，学者们进行了大量的研究．例如：Gharaei等[3]通过基于中间代理的方式设计了节点充电方案，大幅提高了网络的性能和寿命；Kashtriya等[4]通过一种能量机制，合理地安排节点的唤醒和休眠；Ramamurthy等[5]提出在均匀网格上放置传感器的高效方法，能够显著提高能量效率，降低网络成本．此外，博弈论强化学习方法具有对复杂环境干扰的鲁棒性，同时也能够降低通信需求和提高可扩展性．因此，近年来不少研究者推动采用博弈论的方法来解决分布式覆盖的复杂问题．在博弈论强化学习方法当中，覆盖问题被模拟成一个资源分配问题．传感器节点的目标都是从环境中获得最大的覆盖收益，因此须要为覆盖问题设置合理的效用函数，并且保证效用函数能够收敛到纳什均衡．此外，在收敛情况下，如何在提高目标区域的覆盖率的同时节约能量也是须要解决的问题．Zheng等[6]在考虑能量成本的情况下，利用节点跟随的方法探索感兴趣的区域；Zhu等[7]提出了两种分布式学习算法，传感器节点每一轮学习中只须得到试验动作的效用值和前两次迭代过程中较大的效用值，这种算法能保证收敛到纳什均衡；Yao等[8]利用博弈论和覆盖优化的多跳路由协议，设计了聚类博弈和集群簇头覆盖策略，降低了数据传输能耗；Rahili等[9]提出了一种基于博弈论的学习算法解决覆盖问题，假设传感器节点仅与邻居节点通信，并且用它们相互之间的本地信息进行决策，随后为节点设计合适的效用函数，使用强化学习方法去求解博弈问题，最终可以实现全局最优配置．虽然，上述工作在解决覆盖问题时，都很好地考虑了能量消耗问题，但是其使用的节点覆盖模型是较为理想的布尔圆盘模型，忽略了覆盖环境中传感器节点的协同性和相关性．为了解决上述问题，本研究提出一种基于强化学习的物联网可信信息覆盖优化算法，算法采用可信信息覆盖模型，充分利用了节点协同和环境的空间相关性，提高网络的覆盖率．算法基于博弈论强化学习方法，将覆盖问题建模成一个势博弈，并用二进制对数线性强化学习方法求解模型．该算法在设计效用函数时，考虑了奖励分配规则和能量消耗，节点仅与自己的邻居节点进行通信，无须向所有节点传递信息，充分降低了通信能耗．1 可信信息覆盖模型针对复杂覆盖问题，大多数研究将圆盘模型作为基本覆盖模型，该模型不能准确地反映传感器感测功能与被感测环境变量之间复杂的空间相关性．本研究采用Wang等[10]提出的可信信息覆盖(confident information coverage，CIC)模型作为基本覆盖模型，通过多个节点之间的协同感测确认目标检测点的覆盖情况；并且考虑了其他覆盖模型中未考虑的环境变量所固有的空间特性，根据变程对不同环境变量的空间特性进行量化，制定覆盖标准，从而提高覆盖可信度．CIC模型详细定义为：在一个随机场中，给定一个重建函数f，如果该随机场中一个空间位置点x上的重建信息ϕ(x)在时域上的均方根误差均值小于等于网络用户给定的误差阈值ε0，即对于某一空间位置点x的重建信息只要满足ϕ(x)≤ε0，就可以判定该空间位置点x被可信信息覆盖．在实际应用场景中，x的均方根误差(RMSE)计算公式为ϕ(x)=∑i=1nλiγ(pi,x)+z(x)，(1)式中：λi为克里金插值权重系数，且所有权重系数之和为1；γ(pi,x)为高斯变差函数[10]，用来描述采样数据之间的空间相关性；z(x)为拉格朗日乘数器．可信信息覆盖模型如图1所示，图中r为圆盘模型的感知半径．在自由空间中，蓝色圆形区域为以节点为中心的圆盘模型，在考虑节点协同和环境变量的空间特性后，绿色实线围住的区域为节点s1和s2协同感知的可信信息覆盖区域，红色实线围住的区域为s1，s2和s3协同感知的可信信息覆盖区域，因此点p2满足可信信息覆盖重建条件，从而可以被可信信息覆盖．10.13245/j.hust.230201.F001图1可信信息覆盖模型2 势博弈一个基于状态的势博弈可以表示为一个三元函数M:=N,A,U[11]，其中：N={n1,n2, …,ni}为所有传感器节点的集合；集合A=∏i=1nAi为整个动作向量空间；U={u1,u2,…,ui}为效用函数的集合．基于状态的势博弈须要满足以下条件．a．在给定动作空间s*:=(si*,s-i*)情况下，其中si*,s-i*分别为节点i的试验动作集合和除节点i以外其余节点的试验动作集合，对于任意的i∈N和节点i任意的动作集合si∈Ai都能够满足势博弈并收敛到一个纳什均衡，使u(s*)≥u(si,s-i*)成立；b．在一个势函数为Ω的势博弈中，对于任意i∈N，任意s-i∈A-i及每一对si,s-i∈Ai，满足Ω(si,s-i)-Ω(si*,s-i)=u(si,s-i)-u(si*,s-i)，其中：s-i为除节点i以外其余节点的动作集合；A-i=∏j≠1Aj为除节点i以外的其余节点动作向量空间[12]．在势博弈中，当能够满足至少一个纳什均衡的情况下，所有选择的动作都是唯一的，并且所选动作都能够实现最大化收益．3 强化学习强化学习赋予机器自我不断学习的能力，在不断的与陌生环境的交互过程中，调整或者改变策略从而从环境中获取最大的收益，原理如图2所示．10.13245/j.hust.230201.F002图2强化学习原理图在物联网中，每个节点都被随机地部署在任务区域内，每个节点初始状态是随机的，在学习过程中，节点的可选动作集是变化的．为了保证算法能够收敛到纳什均衡，选择二进制对数线性学习算法作为求解博弈问题的方法[13]．使用二进制对数线性强化学习方法可以适应同步更新、时变动作集及玩家可用信息的限制．在二进制对数线性强化学习方法中，可用动作集须要满足两个假设[12]：一个是可行性，对于任意一个选择去学习的节点，本轮学习所选动作与该节点上一轮学习所选动作有关；另一个是可逆性，对于任意节点i∈N和任意相邻时刻的两个动作ai(t-1)和ai(t)，满足ai(t-1)∈ Ci(ai(t))⇔ai(t)∈Ci(ai(t-1))，其中：Ci(ai(t))为与当前时刻动作ai(t)相关的函数，表示节点t-1时刻的可用动作集；Ci(ai(t-1))为与先前时刻动作ai(t-1)有关的函数，表示节点t时刻的可用动作集．4 基于强化学习的可信信息覆盖4.1　任务空间假设一个二维凸平面任务空间被划分为若干个正方形网格，每个网格的面积都是单位1，其中心点坐标为c，并且用集合C表示所有的中心点坐标．在整个任务空间中，每个中心点坐标为c的正方形网格拥有恒定的覆盖价值，并且每个正方形网格代表一种状态．所有的节点随机地部署在C中并根据设定好的移动规则去寻找有价值的区域．在任务空间中，通过设置整个物联网的覆盖价值，给每个单位网格分配一个vc≥0的常数，当vc=0时，这个网格区域没有覆盖价值或者没有重要的事件发生．vc越大，该网格区域的覆盖价值就越高．当节点在学习时，随机选择一个动作，位置信息可以获得该位置网格区域的覆盖价值，即传感器节点所获得的收益．采用对角线分布来模拟任务空间的价值分布，有如下优势．首先，在真实场景中，区域中心位置发生的事件概率更高；然后，可以避免节点在边缘区域陷入移动的死循环．图3为覆盖价值分布示意图，图中：X为部署节点在任务空间中的横坐标；Y为部署节点在任务空间中的纵坐标；W为覆盖价值．每个单位网格都有一个恒定的覆盖价值，表示该网格区域发生事件的概率大小．10.13245/j.hust.230201.F003图3覆盖价值分布示意图4.2　效用函数的设计合理的效用函数是保证算法能够收敛到纳什均衡的关键．算法中，效用函数包含奖励的分配规则和能量消耗两方面．选择边缘分布奖励规则来计算节点的收益．文献[14]证明了边缘分布奖励分配规则拥有良好的收敛性．在边缘分布这种奖励分配规则下，节点收益的计算公式为ur(i,s)=or(s)-or(s\{i})；(2)or(s)=∑c∈m(ai)⋂Cvc，(3)式中：ur(i,s)为节点收益，其中s=(ai,a-i)，ai为节点i选择的动作，a-i为节点i所选动作外的其他动作；m(ai)为节点i更新动作后的覆盖区域；or(s)为节点i选择动作ai的覆盖收益；or(s\{i})为除节点i所选动作外的其他动作的覆盖收益．节点的能耗主要包括传感器节点移动和感知产生的能量损耗[15]．感知能耗和移动能耗的计算公式为eis=hs(air)2; (4)eim=hmd(aip(t),aip(t-1)), (5)式中：hs和hm分别为感知能耗系数和移动能耗系数；air为每个节点的感知半径；aip(t)和aip(t-1)为节点i相邻学习时刻的位置．基于节点收益和能耗，得到效用函数，该效用函数可以用来评价节点收益与能量消耗之间的均衡关系，即Ui(s,aip(t-1))=ur(i,s)-eis-eim．(6)由于效用函数中新增了能量参数，因此须证明该效用函数能够收敛到纳什均衡．文献[12]详细证明了势函数为Ω=ur(i,s)-eis-eim的覆盖游戏为势博弈．4.3　基于可信信息覆盖的博弈论强化学习算法当算法利用二进制对数线性强化学习方法求解基于状态的势博弈时，可以计算选择试验动作ail的概率和选择先前动作ai(t-1)的概率，即A1=exp(τ-1Ui(ai(t-1),aip(t-2)));A2=exp(τ-1Ui(ail(t),a-i(t-1),aip(t-1));piai(t-1)=A1A1+A2;piail=A2A1+A2, (7)式中：Ui(ai(t-1),aip(t-2))为选择先前动作ai(t-1)的效用值；Ui(ail(t),a-i(t-1),aip(t-1)为选择试验动作ail的效用值；piai(t-1)为选择先前动作ai(t-1)的概率；piail为选择试验动作ail的概率；τ为一个大于0的常数，决定节点在随机选择动作过程中，选中次优动作的概率，当然这种概率是比较小的，因此这种逃避非最佳动作的机制，可以在学习中更好地收敛到纳什均衡[14]．在进行一轮学习过后，相应节点的状态发生了改变，未选择的节点还是处在原位置上．此时，根据式(1)可以计算每个重建点的RMSE值[10]，从而判断边长为变程大小的正方形网格是否被可信信息覆盖，根据下式得到可信信息覆盖下的覆盖区域面积mC，进一步计算出可信信息覆盖下的覆盖价值，mC=α2    (ϕ(x)≤ε0);0    (其他), (8)式中α为可信信息覆盖模型的变程[10]．算法1 基于强化学习的物联网可信信息覆盖优化算法初始化任务空间宽度X、任务空间长度Y、变程α、迭代次数T、节点数目N、均方根误差阈值ε0、感知能耗系数hs、移动能耗系数hm及学习参数τ．步骤1 确定随机部署下各传感器节点i的位置aip(1)和感知半径air；通过式(2)和(3)可以计算出初始时刻的可信信息覆盖价值w(1)．步骤2 在第t(t1)轮学习周期中，随机选择一个传感器节点进行学习．a．选中的传感器节点随机从可选动作集F中选择一个试验动作ail；b．根据式(4)和(5)分别计算出em和es；c．通过式(2)和(3)计算出ai(t-1)和ail的效用值U1和U2；d．通过式(7)计算选择ai(t-1)的概率piai(t-1)和选择ail的概率piail，若piailpiai(t-1)，则更新该选中传感器节点的位置aip(t)，并通过式(2)和(3)重新计算可信信息覆盖价值w(t)．步骤3 待节点位置更新完毕，下一轮学习周期开始，t值加1．重复执行步骤2，直至学习周期t到达迭代次数T，学习任务结束，在收敛状态下的集合W={w(1),w(2),…,w(t)}即为整个学习过程的覆盖价值曲线．5 实验结果为了评估本研究所提出的基于强化学习的物联网可信信息覆盖优化算法(DCIC-GTRL)的有效性和合理性，将所提算法和另外两种算法进行对比，分别就网络的覆盖率、覆盖价值及收敛情况进行对比分析．一种是基于博弈论和强化学习的分布式圆盘部署方法，即分布式异构同步覆盖学习算法(DDC-GTRL)，该算法采用布尔圆盘模型定义覆盖；另一种是基于圆盘模型的中心点部署方法(Random)，该算法采用的是确定性部署．5.1　算法在覆盖价值维度的仿真分析5.1.1　不同节点数目的覆盖价值收敛情况图4为不同节点数目下的覆盖价值收敛情况．设置了初始节点数目为8，9，10，12的四组实验，CIC模型的变程为4，RMSE阈值为0.5，任务区间为20×20，迭代次数为1 500，感知能耗系数为3×10-5，移动能耗系数为3×10-4，学习参数为5×10-3．从图4中可以看出：本研究提出的算法在性能上更为优越，在收敛状态下，四种节点数目情况下的覆盖价值都要比对比算法高出约一倍．10.13245/j.hust.230201.F004图4不同节点数目下的覆盖价值收敛曲线5.1.2　不同RMSE阈值的覆盖价值收敛情况图5为不同RMSE阈值(ε0)下的覆盖价值收敛情况，验证RMSE阈值对网络覆盖价值收敛的影响．分别设置了RMSE为0.3，0.5，0.6及0.8四组对比实验，初始节点数目为10，任务区间为20×20，CIC模型相应的变程设置为4．在图5中可以看到：本文算法在收敛状态下的覆盖价值相对于对比算法有较大提高，这是因为RMSE阈值的设定对可信信息覆盖模型的覆盖范围有很大影响，RMSE阈值变化，可信信息覆盖区域也会跟着变化．10.13245/j.hust.230201.F005图5不同RMSE阈值的覆盖价值收敛曲线图5.1.3　不同任务空间的覆盖价值收敛情况图6为不同任务空间大小的覆盖价值收敛情况．在实验中，初始节点数目为10．任务区间为20×20和30×30，并且CIC模型相应的变程为4和6．在图6中可以看出：本文算法要优于对比算法，并且随着任务空间的变大，其算法收敛的越慢，可见任务空间的大小会对算法的收敛产生一定的影响．10.13245/j.hust.230201.F006图6不同任务空间的覆盖价值收敛曲线图5.2　算法在覆盖率维度的仿真分析图7为不同节点数目下整个网络覆盖率的变化曲线，图中：T为最大迭代次数；R为覆盖率．在实验中，设置了初始节点数目为8和10的对比实验，任务空间的大小为20×20，RMSE阈值为0.5，CIC模型的变程设置为4．10.13245/j.hust.230201.F007图7不同节点数目的覆盖率收敛曲线图从图7中可以看出：在收敛情况下，本文算法要优于对比算法，既保证了覆盖率和能耗之间的平衡，同时又能提高网络覆盖率．5.3　算法在其他维度的仿真分析图8为节点的最终位置图，图中X和Y分别为部署节点在任务空间中的横、纵坐标．从图8中可以看出：所有传感器节点都集中在中间区域，即覆盖价值最高的网格，与本研究设定的网络覆盖价值分布相对应，从而验证了本研究所设计的基于强化学习的物联网可信信息覆盖优化算法的合理性和准确性．10.13245/j.hust.230201.F008图8最终配置图6 结语本研究针对物联网的覆盖优化问题，提出了一种新的基于强化学习的可信信息覆盖优化算法，在考虑能量消耗的情况下，实现整个网络的覆盖价值最大化．算法充分利用了节点之间的协同和空间相关性，并采用博弈论强化学习均衡了节点覆盖和能量损耗，具有良好的收敛性，并且能够在保证收敛到纳什均衡的同时提供更大的全局覆盖率和覆盖价值．但该强化学习方法会有一定的几率选择到次优动作，导致节点的最终位置是一种局部最优配置，将在未来的工作中继续对此进行优化．