[發明專利]基于Barzilai-Borwein梯度法的無線傳感器網絡分布式定位方法

有效

• 申請號: 202010103565.8
• 申請日: 2020-02-20
• 公開（公告）號: CN111314847B
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 蔣俊正;李楊劍;趙海兵
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: H04W4/02
• 分類號: H04W4/02;H04W64/00;H04W84/18
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 覃永峰

1.基于Barzilai-Borwein梯度法的無線傳感器網絡分布式定位方法，其特征在于，包括如下步驟：

1)在需要檢測的區域內隨機部署N個傳感器節點，構成無線傳感器網絡，對其中m個節點添加BDS或GPS模塊作為已知位置節點，剩余的n個節點作為未知位置節點，即待定位節點；

2)假定無線傳感器網絡中部署的所有傳感器節點為一個集合，如果傳感器節點之間可以直接相互通信，則可看作有一條邊連接，從而可將整個無線傳感器網絡看做為一個全局的無向圖，并將傳感器節點的定位問題歸結為無約束優化問題，即：在監控區域維空間中部署傳感器節點，這些節點構成WSN，WSN中共有N個節點，其中有m個LA節點，n個LU節點，LA節點位置表示為a_λ，λ＝1，2，3，…，m；LU節點位置表示為x_i，i＝1，2，3，…，n，LU節點i與節點j之間的歐式距離表示為d_ij；LU節點i與LA節點λ之間的歐式距離表示為d_iλ，假設傳感器節點的最大通信半徑為R，則對于每個LU節點i定義兩個集合：和其中表示在通信半徑R內，可以直接和節點i通信的LU節點鄰居集合；表示在通信半徑R內，可以直接和節點i通信的LA節點鄰居集合，則將WSN中節點定位問題可以歸結為一個無約束的優化問題：

其中，ω_ij和ω_iλ是權重，d_ij和d_iλ是帶噪聲的測距；

3)設與未知位置節點直接相連的節點為鄰居節點，以未知位置節點為中心，以未知位置節點的通信半徑作圓，將圓內所有節點和節點之間的邊記為一個子圖，從而將無線傳感器網絡構成的全局無向圖分解為n個部分重疊的子圖，然后對步驟2)中歸結出的無約束優化問題進行重新構造，進而給出子圖中的無約束優化問題：WSN可由無向圖來描述，其中，表示WSN中LU節點集合，表示WSN中LA節點集合，表示節點之間邊的集合，其中，e_iλ表示LU節點i與LA節點λ之間可以直接通信，e_ij表示LU節點i和LU節點j之間可以直接通信，傳感器節點只能與通信半徑R內的節點直接通信，采用以LU節點為中心將WSN劃分為部分重疊的子圖：

其中，表示子圖G_s中LU節點的集合，表示子圖G_s中LA節點集合，表示集合中節點之間邊的集合，然后，將定位問題公式(1)重新構造為：

其中，d_ij和d_iλ分別為子圖G_s中，采用測距方式獲得的LU節點之間，以及LU節點與LA節點之間的距離，測得的距離并非節點之間的真實距離，而是帶噪聲測距，噪聲模型如公式(5)、公式(6)所示，LA節點即使加上GPS模塊，得到的LA位置也是有噪聲的，噪聲模型如公式(7)所示，

d_ij＝||x_i-x_j||₂·|1+τ₁ε_ij| (5)，

d_iλ＝||x_i-a_λ||₂·|1+τ₁ε_iλ| (6)，

其中，τ₁∈[0，1]是距離噪聲因子，用于控制測距之間的噪聲強度；是LA節點的真實位置；τ₂∈[0，1]是LA節點位置噪聲因子，用于控制LA節點位置的噪聲強度；ε_ij、ε_iλ和ε_λ是隨機噪聲，是一個正態隨機變量N(0，1)，

公式(4)中ω_ij和ω_iλ是子圖G_s中根據節點之間距離的反比取的歸一化權重，權重分別為：

將WSN構成的全局無向圖分解為部分重疊的子圖后，根據公式(4)，可以將定位問題分解為一系列子圖G_s內的定位問題，采用分布式方法進行求解，子圖G_s內的定位問題如公式(10)所示：

其中，為子圖G_s中LU節點的集合；為子圖G_s中節點之間邊的集合；d_ij為子圖G_s中LU節點i和j之間的帶噪聲測距；d_iλ為子圖G_s中LU節點i和LA節點λ之間的帶噪聲測距，使用表示子圖G_s中LU節點數目；表示子圖G_s中LA節點數目；x_i＝[x_i1，x_i2]表示LU節點x_i的坐標；a_λ＝[a_λ1，a_λ2]表示LA節點a_λ的坐標；表示子圖G_s中所有LU節點坐標構成的列向量；表示子圖G_s中所有LA節點坐標構成的列向量；表示2n₁×2n₁的單位矩陣；表示2n₂×2n₂的單位矩陣；e_i1和e_i2分別表示的第2i-1列和第2i列；e_λ1和e_λ2分別表示的第2λ-1列和第2λ列，根據上述定義，則傳感器節點間的真實距離可寫為：

其中，

A＝(e_i1-e_j1)(e_i1-e_j1)^T+(e_i2-e_j2)(e_i2-e_j2)^T (13)，

公式(10)可以寫為：

f_s(x)的梯度向量為：

4)采用極大似然估計法，估計出未知位置節點的初始位置p^(t)，將初始位置p^(t)作為步驟3)中未知位置節點的初始值，其中，t表示迭代次數，令t＝0：假設D點為LU節點，坐標為(xy，在D點的通信半徑R內有m個LA節點，坐標分別為(x₁，y₁)，(x₂，y₂)，(x₃，y₃)，…，(x_m，y_m)，采用測距法測得D點至m個LA節點的帶噪聲測距分別為d₁，d₂，d₃，…，d_m，則測得的距離與D點坐標和m個LA節點坐標之間有以下關系：

將前m-1個方程與第m分方程相減，得到以下方程組：

公式(21)可寫為矩陣形式：

AX＝b (22)，

其中，

最小二乘解即為LU節點D的估計值：

采用以下規則估計LU節點的初始位置：

1-4)當LU節點有3個或3個以上的LA鄰居時，使用最大似然估計法計算LU節點的初始位置；

2-4)當LU節點有1-2個LA鄰居時，將距離LU節點最近的LA節點的位置作為其初始位置；

3-4)當LU節點沒有LA鄰居時，將傳感器節點分布區域的中心作為LU節點的初始位置；

5)采用分布式方法對步驟3)中歸結出的優化問題公式(4)進行迭代求解，過程為：

1-5)采用Barziiai-Borwein梯度法對步驟3)中歸結出的子圖G_s中的優化問題即公式(10)進行求解，梯度法計算步長公式如下：

如果k＝0，則通過回溯直線搜索法確定步長α₀，設置參數μ＝0.2，β＝0.5，α₀＝1，若下式成立，則令α₀＝βα₀，循環直到下式不成立：

子圖中使用Barzilai-Borwein梯度法進行優化求解的過程如下：

1-1-5)使用極大似然估計法，粗略獲得LU節點的初始值，提取子圖G_s中LU節點的位置x_k，作為初始值，設k＝0，表示第k次迭代；

2-1-5)計算搜索方向q_k：

3-1-5)計算步長：如果k＝0，通過回溯直線搜索法確定步長α₀；否則通過公式(27)計算步長α_k；

4-1-5)更新子圖G_s中LU節點位置：x_k+1＝x_k+α_kq_k；

5-1-5)判斷迭代終止條件：如果滿足ε是一個正數，或k＞100，則終止迭代，x_k+1即為迭代結果，否則令k＝k+1返回到步驟2-1-5)；

2-5)采用子圖融合的方法，對部分重疊的子圖進行融合，得到第t+1次迭代的未知位置節點的估計位置p^(t+1)，具體為：子圖融合公式如下：

其中，表示包含LU節點i的子圖索引集合；x_i，s表示子圖G_s中LU節點i的坐標；表示LU節點i融合之后的坐標；

3-5)迭代終止：若δ是正數，δ取1e-2，則p^(t+1)為最終估計出的未知位置節點的位置，否則，將p^(t+1)作為新的初始值，并令t＝t+1，返回至步驟1-5)繼續迭代，其中，i＝1，2，3，…，n表示無線傳感器網絡中未知位置節點的標號；表示未知位置節點i在第t+1次迭代的估計值，p^(t)表示未知位置節點i在第t次迭代的估計值。