网络定位中基于联盟博弈的功率分配方法

摘要

本发明公开了一种网络定位中基于联盟博弈的功率分配方法。该功率分配方法主要包括如下过程：以几何精度因子作为定位精度的性能指标，在节点功率分配满足一定公平性原则的前提下，构建了基于联盟的无线传感器网络定位功率消耗优化模型，并给出了几何精度因子的具体表达式；针对几何精度因子值计算复杂的问题，通过设计联盟博弈的形成算法、求解该优化模型的效用函数，提出优化模型的改进模型。在保证定位精度的前提下，以双面双边测距协议为基础，提出了一种求解联盟和功率分配的分布式测量方法。本发明方法可应用于无线传感器网络定位阶段的功率分配优化问题。

主权项

网络定位中基于联盟博弈的功率分配方法，其特征在于，包括如下步骤：s1建立基于联盟的无线传感器网络定位功率消耗优化模型定义联盟：设Ν＝{1,2,…N}表示传感网中的源节点集，其中N表示源节点的数目，Ν的任意一个非空子集称为Ν的一个联盟；只包含一个节点的联盟称为单联盟；对于给定的Ν的一个联盟，可通过定义一个满足$s_i=\{\begin{array}{cc}0,& i\in S\\ 1,& i\notin S\end{array},\forall i\in N$的向量s∈{0,1}^N来表示；用于定位第k个目标节点的非空的源节点的集合是一个联盟，记为S_k；定义联盟结构：设S_k1,S_k2,…,S_kn为n个联盟，如果满足则称{S_k1,S_k2,…,S_kn}为N的一个联盟结构；记Ν所有的联盟结构的集合为Τ；在无线传感器网络定位中，联盟S_k中的所有源节点通过发射包含自身位置信息的信号至第k个目标节点，设第i个源节点消耗的功率为p_i，其中p_i∈[0,P]，P为源节点的最大发射功率；设记录测量值所需的时间为T_s，故其消耗的能量为p_iT_s，所有网络节点进行一次测量所需耗费的能量为基于联盟的无线传感器网络定位功率消耗优化模型可表示为：$\underset{Y\in T}{\underset{{}_{p\in {[0,P]}^N}}{min}}\frac{\underset{S\in Y}{\Sigma }\left(\underset{i\in S}{\Sigma }{p}_i\right)}{N}$$s.t.{\mathrm{GDOP}}_k\le {\tilde{O}}_k,\forall k\in K$$0\le p_i\le {p^{\prime }}_i,\forall i\in N---\left(1\right)$其中，p＝(p₁,p₂…p_N)^T为功率的分配向量，目标函数是某个联盟结构中各节点所耗费的功率之和，是定位时所需满足的定位精度值，GDOP_k为对S_k联盟而说的几何精度因子，p'_i为第i个源节点分配得到的功率的上限；约束条件表明该联盟的几何精度因子不超过即定位误差控制在一定范围内；假设节点组成了联盟结构Y,节点的功率分配向量为p，如果所有的传感器无法形成联盟使得节点的功率减小，则称功率分配向量p是公平的；因此功率分配向量p是公平的当且仅当其满足：其中，对目标节点k预先设定的精度而言，G(S'_k)为S'_k中的最小功率：$G\left({S^{\prime }}_k\right)=\underset{{}_{\{{p^{\prime }}_i,i\in {S^{\prime }}_k\}}}{min}\underset{r\in {S^{\prime }}_k}{\Sigma }{p^{\prime }}_i---\left(3\right)$$s.t.{\mathrm{GDOP}}_k\le {\tilde{O}}_k$如果可行集为空，则设G(S'_k)＝∞；在满足公平性条件即式(2)的前提下求解优化模型即式(1)可得到最优的功率分配方案；s2几何精度因子的计算假设一个目标节点通过含噪声的距离ρ_i的测量来估计它的位置，即：${\rho }_i~N\left({\rho }_i\right(x),{\sigma }_{{\rho }_i}^2),---\left(4\right)$其中，观察值的标准差依赖于TOA算法测量的标准差，即：${\sigma }_{{\rho }_i}=\frac{c·{\sigma }_{{\mathrm{TOA}}_i}}{4},---\left(5\right)$其中，c为光速常量，为TOA测量中的标准差，因数4表示从源节点到目标节点两个来回，上述变量通过对称双面双向测距协议用来获得距离估计；目标节点的位置通过最小二乘法估计得到，x表示目标节点的实际位置坐标，表示第i个源节点的坐标，目标节点的坐标估计值是使得均方差最小的坐标：$\hat{x}=\arg \underset{{}_x}{min}\left\{\underset{i\in N}{\Sigma }{({\rho }_i-||x-x_a^{\left(i\right)}|\left|\right)}^2\right\},---\left(6\right)$这个优化问题基于一个摩尔－彭若斯广义逆矩阵的闭合解为：$\tilde{x}={\left(H^{T}H\right)}^{-1}{H}^{T}b,---\left(7\right)$其中，N维向量b定义为：b＝[ρ₁‑ρ₁(x⁰),…ρ_N‑ρ_N(x⁰)]^T,   (8)N*2阶矩阵Η为：$H\left(\begin{array}{cc}\frac{x_a^{\left(1\right)}-x}{{\rho }_1\left(x\right)}& \frac{y_a^{\left(1\right)}-y}{{\rho }_1\left(x\right)}\\ \frac{x_a^{\left(2\right)}-x}{{\rho }_2\left(x\right)}& \frac{y_a^{\left(2\right)}-y}{{\rho }_2\left(x\right)}\\ .& .\\ .& .\\ .& .\\ \frac{x_a^{\left(N\right)}-x}{{\rho }_N\left(x\right)}& \frac{y_a^{\left(N\right)}-y}{{\rho }_N\left(x\right)}\end{array}\right){|}_{x=x^0},---\left(9\right)$其中，N为源节点集合Ν的基数，即对目标节点测量的次数；求解式(7)需要初始化未知的目标节点坐标，记作x⁰；式(7)中的最小二乘解与以下方差矩阵有关：$C_{\hat{x}}={\left(H^T{\Sigma }^{-1}H\right)}^{-1},---\left(10\right)$其中，对角矩阵为：$\Sigma =diag({\sigma }_{{\rho }_1}^2,\mathrm{...}{\sigma }_{\rho N}^2)---\left(11\right)$式(11)等式右边括号内的各个参数是式(3)中每一次距离测量时的方差；几何精度因子定义如下：$GDOP=\sqrt{Tr\left\{{\left(H^T{\Sigma }^{-1}H\right)}^{-1}\right\}},---\left(12\right)$其中Tr{·}表示迹算子，平均的克拉姆‑拉奥下界的计算公式为以下不等式右侧的表达式：${\sigma }_{{\rho }_i}=K_i\sqrt{\frac{c^2{N}_0}{16{\pi }^2{\mathrm{BT}}_S{f}_c^2{L}_i{p}_i}}\ge \sqrt{\frac{c^2{N}_0}{16{\pi }^2{\mathrm{BT}}_S{f}_c^2{L}_i{p}_i}},---\left(13\right)$其中，B是信号带宽，T_s是信号的持续时间，f_c是中心频率，L_i＝(λ/4πρ_i)²是路径损失，ρ_i为距离，λ为频率，p_i是第i个源节点的传输功率，N₀是噪声的密度；s3联盟博弈的形成算法一个目标节点和多个源节点的无线传感网中源节点联盟的形成算法如下：考虑只有一个目标节点的情况，联盟S中的所有源节点用于发射信号至该目标节点，将所有的源节点都加入到联盟S中，即源节点数量a＝N,对所有的源节点进行传输功率的分配求最优分配，当一个源节点分配到的功率等于0时表示该源节点不在该联盟中，即可求得定位该目标节点的源节点的联盟，这时候相当于所有的源节点组成了一个大联盟；这时候的源节点功率分配问题可用一个三元组Γ(Ν，Ρ，υ)来表示，其中各元素表示如下：(1)Ν是N个博弈对象的集合，即无线传感网中的源节点的联盟；(2)Ρ是博弈的策略集，是所采用的功率分配策略，即各源节点的功率分配，其中第i个源节点消耗的功率为p_i，p_i∈[0,P]，P为节点的最大发射功率限制，令P_‑i表示除了第i个源节点以外的其他源节点的功率分配；(3)v_i是第i个源节点的效用函数，表示对给定的功率分配策略，第i个源节点的收益，υ＝{v_i}_i∈Ν是N个源节点效用函数的集合；用几何精度因子GDOP的绝对值和第i个源节点分配到的功率值p_i来表示效用函数；定义以下的效用函数以满足上述变量之间的变化关系：$v_i(p_i,p_{-i})=\frac{A}{(1-\alpha )\sqrt{g\left(p\right)}+{\mathrm{\alpha p}}_i}---\left(14\right)$其中，0≤α≤1表示在功率和误差之间的权衡，即功率对效用函数的影响所占的比例，每一个源节点均通过自身的电池的状态控制这个参数的值；A≥1表示对效用函数的值的修正，g(p)＝(GDOP(p))²表示GDOP的平方；博弈的类型是通过效用函数定义的，如果效用函数满足超模性，则该博弈就可以称为超模博弈；s4联盟博弈的扩展当联盟内有多个目标节点，效用函数和特征函数有所不同；依然考虑三元组Γ(Ν，Ρ，υ)，此时效用函数如下式(15)，此时效用函数依然满足超模性；$v_i(p_i,p_{-i})=\frac{A}{(1-\alpha )\sqrt{\frac{\underset{j-1}{\overset{M}{\Sigma }}{g}_j\left(p\right)}{M}}+{\mathrm{\alpha p}}_i},---\left(15\right)$s5改进的优化模型通过把效用函数作为目标函数来改写式(1)，即可得如下优化模型：$\underset{\underset{Y\in T}{p\in {[0,P]}^N}}{max}\frac{\underset{S\in Y}{\Sigma }\left(\underset{i\in S}{\Sigma }{v}_i\right)}{N}---\left(16\right)$$s.t.0\le p_i\le {p^{\prime }}_i,\forall i\in N$上述优化模型也可用各联盟的特征方程表示为：$\underset{\underset{Y\in T}{p\in {[0,P]}^N}}{max}\frac{\underset{S\in Y}{\Sigma }u\left(p\right)}{N}---\left(17\right)$$s.t.0\le p_i\le {p^{\prime }}_i,\forall i\in N$把优化模型的目标函数写成联盟的特征函数的累加和，在求解时先求解联盟的分解，然后得出每个联盟的特征函数，最后求解优化模型；上述的优化模型使用的是特征函数；令$n_i(p_i,p_{-i})=(1-\alpha )\sqrt{g\left(p\right)}+\alpha p_i---\left(18\right)$则当特征函数的值越大时，式(18)的值越小，故把优化模型改写为：$\underset{\underset{Y\in T}{p\in {[0,P]}^N}}{min}\frac{\underset{S\in Y}{\Sigma }\left(\underset{i\in S}{\Sigma }{n}_i\right)}{N}---\left(19\right)$$s.t.0\le p_i\le {p^{\prime }}_i,\forall i\in N$s6基于超模博弈的功率分配和联盟形成算法，算法的具体步骤如下：s61、初始化，目标节点发送测距请求信息s62、迭代次数记为n＝1,总共所需的迭代次数为N_it·|k|次；s63、当n的值小于迭代次数且没有收到测距终止信号时，执行步骤s64，否则执行步骤s611；s64、i为收到目标节点帧的顺序标志，收到请求信息的第i个源节点发送帧其中包含如下信息：(1)该源节点得到的功率值p_i；(2)n＝1时，即初始化时包含初始源节点坐标信息，当3≤i≤k时记录定位该目标节点的联盟的向量的值为1，即s_i＝1，计算更新g_i(p)值；s65、目标节点收到源节点的测距响应帧后，向源节点发送确认帧s66、源节点发送确认响应帧s67、目标节点收到确认响应帧后，计算出距离估计值ρ_i，收到的最大的i值即为目前收到的帧数，满足3≤i≤k时用最小二乘法计算和Η的值，计算g(p)的值；s68、目标节点向源节点发送确认帧其中包含步骤s67中计算得到的各数值；s69、源节点计算Η_i和g_i(p)的值，并替换到Η和g(p)中更新，利用优化算法得到使效应函数最大的功率分配值p_i并更新功率分配向量；s610、判断源节点收到目标节点帧的顺序标志i,i＝k时令i＝1,n＝n+1迭代结束，否则i＝i+1继续判断其他源节点；s611、测距结束。