[發(fā)明專利]移動(dòng)無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)自適應(yīng)分布式重聚類方法

有效

• 申請?zhí)枺?/td>: 201510638551.5
• 申請日: 2015-09-29
• 公開（公告）號: CN105263149B
• 公開（公告）日: 2018-11-16
• 發(fā)明（設(shè)計(jì)）人: 徐超杰;俞暉;劉中令;夏俊
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: H04W16/24
• 分類號: H04W16/24;H04W40/00;H04W24/00;H04W84/18
• 代理公司: 上海漢聲知識(shí)產(chǎn)權(quán)代理有限公司 31236
• 代理人: 郭國中

1.一種移動(dòng)無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)自適應(yīng)分布式重聚類方法，其特征在于，包括如下步驟：

步驟A：在已經(jīng)聚類成簇的移動(dòng)無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)在移動(dòng)過程中，節(jié)點(diǎn)根據(jù)慣性傳感器的傳感數(shù)據(jù)，對每個(gè)時(shí)刻的自身位置進(jìn)行估計(jì)，得到每個(gè)時(shí)刻的估計(jì)位置；

步驟B：每個(gè)重聚類周期開始時(shí)，節(jié)點(diǎn)依據(jù)自身移動(dòng)所遵循的運(yùn)動(dòng)模型以及自身當(dāng)前時(shí)刻的位置，對下一時(shí)刻自身的位置進(jìn)行預(yù)測，得到預(yù)測位置；

步驟C：非簇頭節(jié)點(diǎn)將步驟A中得到的估計(jì)位置發(fā)送給所屬簇的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)整合簇內(nèi)節(jié)點(diǎn)的估計(jì)位置之后與鄰近簇的簇頭節(jié)點(diǎn)通信，并將從鄰近簇的簇頭節(jié)點(diǎn)獲得的估計(jì)位置發(fā)送給簇內(nèi)邊界節(jié)點(diǎn)，邊界節(jié)點(diǎn)對自身是否需要重聚類進(jìn)行評估；

步驟D：非簇頭節(jié)點(diǎn)將步驟B中得到的預(yù)測位置發(fā)送給所屬簇的簇頭節(jié)點(diǎn)，非簇頭節(jié)點(diǎn)中需要重聚類的邊界節(jié)點(diǎn)將重聚類請求發(fā)送給所屬簇的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)獲取簇內(nèi)節(jié)點(diǎn)的預(yù)測位置和重聚類請求信息之后與鄰近簇的簇頭節(jié)點(diǎn)通信，并將從鄰近簇的簇頭節(jié)點(diǎn)獲得的預(yù)測位置、重聚類請求以及自身所屬簇內(nèi)節(jié)點(diǎn)的預(yù)測位置、重聚類請求發(fā)送給需要重聚類的邊界節(jié)點(diǎn)，需要重聚類的邊界節(jié)點(diǎn)完成重聚類；

每個(gè)節(jié)點(diǎn)運(yùn)行粒子濾波算法對移動(dòng)過程中每個(gè)時(shí)刻自身的位置進(jìn)行估計(jì)，通過步驟A執(zhí)行移動(dòng)節(jié)點(diǎn)的位置估計(jì)過程，具體如下：

所述步驟A包括如下步驟：

步驟A1：初始時(shí)刻，對應(yīng)k＝0，節(jié)點(diǎn)的位置為已知，在節(jié)點(diǎn)位置附近隨機(jī)產(chǎn)生N₀個(gè)粒子；表示k＝0對應(yīng)的初始時(shí)刻的第i個(gè)粒子，i∈{1,...,N₀}，的權(quán)重值為

步驟A2：獲得第k-1個(gè)時(shí)刻到第k個(gè)時(shí)刻過程中粒子位置或者節(jié)點(diǎn)估計(jì)位置的更新方程，具體為：

第k個(gè)時(shí)刻時(shí)，其中k≥1，根據(jù)航跡推算法，得到粒子位置或者節(jié)點(diǎn)估計(jì)位置的更新方程為：

其中，s_k表示第k個(gè)時(shí)刻時(shí)的粒子位置或者節(jié)點(diǎn)估計(jì)位置，s_k-1表示第k-1個(gè)時(shí)刻時(shí)的粒子位置或者節(jié)點(diǎn)估計(jì)位置，t表示相鄰時(shí)刻之間時(shí)間間隔的長度，其中假設(shè)每個(gè)時(shí)間間隔內(nèi)節(jié)點(diǎn)速度值與運(yùn)動(dòng)方向不變，v_k-1表示第k-1個(gè)時(shí)間間隔中的節(jié)點(diǎn)速度值，d_k-1表示第k-1個(gè)時(shí)間間隔中的節(jié)點(diǎn)運(yùn)動(dòng)方向，Δd_k表示第k-1個(gè)時(shí)間間隔到第k個(gè)時(shí)間間隔節(jié)點(diǎn)運(yùn)動(dòng)方向的改變值；所述第k-1個(gè)時(shí)間間隔，是指第k-1個(gè)時(shí)刻與第k個(gè)時(shí)刻之間的時(shí)間間隔；

步驟A3：在第k-1個(gè)時(shí)刻到第k個(gè)時(shí)刻的粒子狀態(tài)更新過程，包括粒子本身位置、粒子的權(quán)重值的更新以及粒子發(fā)展出N_evolve個(gè)新粒子來代替自身；在第k個(gè)時(shí)刻時(shí)第i個(gè)新粒子的非歸一化權(quán)重值為新粒子的歸一化權(quán)重值為其中，N_k表示包括所有新粒子在內(nèi)的粒子總數(shù)，N(·)為由第k-1個(gè)時(shí)刻時(shí)的粒子發(fā)展出新粒子的概率，N(·)服從為均值、為方差的高斯分布，表示粒子的歸一化權(quán)重值，N_evolve為預(yù)先設(shè)定的正整數(shù)，粒子表示第k-1個(gè)時(shí)刻時(shí)第i個(gè)粒子，粒子表示第k個(gè)時(shí)刻時(shí)第i個(gè)新粒子；μ_k表示第k個(gè)時(shí)刻時(shí)所述高斯分布的均值，δ_k表示第k個(gè)時(shí)刻時(shí)所述高斯分布的方差，表示第k個(gè)時(shí)刻時(shí)第j個(gè)新粒子；

步驟A4：計(jì)算第k個(gè)時(shí)刻的有效粒子閾值

步驟A5：計(jì)算第k個(gè)時(shí)刻的有效粒子數(shù)目其中，若則為了避免權(quán)重值集中于某些粒子，在引入服從學(xué)生氏t分布的噪聲的情況下重采樣個(gè)粒子，即過濾掉個(gè)粒子中權(quán)重值最小的個(gè)粒子，并將具有最高權(quán)重值的個(gè)粒子重新生成；

步驟A6：計(jì)算第k個(gè)時(shí)刻節(jié)點(diǎn)的估計(jì)位置其中，

所述步驟A4包括如下步驟：

步驟A41：第k個(gè)時(shí)刻，計(jì)算所有粒子的位置與當(dāng)前狀態(tài)下節(jié)點(diǎn)的位置之間的歐氏距離，其中，第k個(gè)時(shí)刻節(jié)點(diǎn)的位置p_k由基于第k-1個(gè)時(shí)刻節(jié)點(diǎn)的估計(jì)位置慣性傳感器的傳感數(shù)據(jù)計(jì)算得到，將這些歐式距離進(jìn)行升序排序，得到升序集合S_d，其中，慣性傳感器的傳感數(shù)據(jù)包括第k-1個(gè)時(shí)間間隔中的節(jié)點(diǎn)速度值v_k-1，第k-1個(gè)時(shí)間間隔中的節(jié)點(diǎn)運(yùn)動(dòng)方向d_k-1，第k-1個(gè)時(shí)間間隔到第k個(gè)時(shí)間間隔節(jié)點(diǎn)運(yùn)動(dòng)方向的改變值Δd_k，p_k的計(jì)算公式為：

步驟A42：計(jì)算升序集合S_d中所有元素的平均值并將升序集合S_d中所有大于平均值的歐式距離按照原順序放入子集升序集合S_d中其余元素則按照原順序放入子集

步驟A43：分別計(jì)算子集中所有元素與子集中前i個(gè)元素的平均值以及中前i個(gè)元素之外的剩余元素的平均值

步驟A44：計(jì)算i及i對應(yīng)的有效粒子閾值的最優(yōu)取值，計(jì)算公式分別為：

其中，為中元素的數(shù)目；

節(jié)點(diǎn)對下一時(shí)刻自身的位置進(jìn)行預(yù)測，通過步驟B執(zhí)行節(jié)點(diǎn)位置預(yù)測過程，步驟B包括如下步驟：

步驟B1：根據(jù)節(jié)點(diǎn)的運(yùn)動(dòng)模型，以及節(jié)點(diǎn)實(shí)際可能出現(xiàn)的運(yùn)動(dòng)情況，并結(jié)合第k-1個(gè)時(shí)間間隔中的節(jié)點(diǎn)速度值v_k-1與節(jié)點(diǎn)運(yùn)動(dòng)方向d_k-1，可以獲得第k個(gè)時(shí)間間隔內(nèi)節(jié)點(diǎn)速度值變化范圍V_range以及相對于節(jié)點(diǎn)運(yùn)動(dòng)方向d_k-1的節(jié)點(diǎn)運(yùn)動(dòng)方向變化范圍D_range；將V_range等間隔離散化為N_v個(gè)速度值，將D_range等間隔離散化為N_d個(gè)方向變化值；

其中，N_v、N_d為正整數(shù)，V_range＝[v_min,v_max]，D_range＝[-θ₁,θ₂]，v_min表示節(jié)點(diǎn)速度值變化范圍的下限，v_max表示節(jié)點(diǎn)速度值變化范圍的上限，θ₁表示運(yùn)動(dòng)方向沿順時(shí)針方向變化最大值，θ₂表示運(yùn)動(dòng)方向沿逆時(shí)針方向變化最大值；

步驟B2：按照如下計(jì)算公式：

根據(jù)第k個(gè)時(shí)刻節(jié)點(diǎn)的估計(jì)位置第k個(gè)時(shí)間間隔內(nèi)節(jié)點(diǎn)第i個(gè)可能的速度值v_i,v_i∈V_range,i∈N_v以及第j個(gè)可能的運(yùn)動(dòng)方向變化值θ_j,θ_j∈D_range,j∈N_d，計(jì)算得到每對v_i與θ_j的組合所對應(yīng)的第k+1個(gè)時(shí)刻節(jié)點(diǎn)可能位置s_ij，獲得由各對v_i與θ_j的組合所對應(yīng)的第k+1個(gè)時(shí)刻節(jié)點(diǎn)可能位置s_ij構(gòu)成的可能位置集合S；由每對v_i、θ_j的概率值p(v_i)、p(θ_j)，得到對應(yīng)s_ij出現(xiàn)的概率值p(s_ij)，p(s_ij)＝p(v_i)·p(θ_j),得到與可能位置集合S中元素一一對應(yīng)的概率值集合P，其中，概率值集合P由各對v_i與θ_j對應(yīng)的概率值p(s_ij)構(gòu)成；

步驟B3：從可能位置集合S中隨機(jī)選取N_rand個(gè)節(jié)點(diǎn)可能位置，N_rand≤N_v，并記錄對應(yīng)N_rand個(gè)節(jié)點(diǎn)可能位置出現(xiàn)的概率值的集合P_rand；將P_rand中的概率值排序，選擇概率值最高的N_sel個(gè)概率值為集合P_sel，并得到N_sel個(gè)概率值對應(yīng)的可能位置集合S_sel；N_sel為正整數(shù)；

步驟B4：歸一化集合P_sel中的概率值得到集合P_norm，則根據(jù)集合S_sel中節(jié)點(diǎn)的可能位置與可能位置對應(yīng)的歸一化概率計(jì)算節(jié)點(diǎn)在第k+1個(gè)時(shí)刻的預(yù)測位置：

其中，s_k+1表示節(jié)點(diǎn)在第k+1個(gè)時(shí)刻的預(yù)測位置，p_i表示集合P_norm中的第i個(gè)元素，s_i表示集合S_sel中的第i個(gè)元素；

邊界節(jié)點(diǎn)對自身是否需要重聚類進(jìn)行評估，通過步驟C執(zhí)行邊界節(jié)點(diǎn)重聚類評估過程，步驟C包括如下步驟：

步驟C1：非簇頭節(jié)點(diǎn)將步驟A中獲得的估計(jì)位置發(fā)送給當(dāng)前所屬簇C_now的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)整合簇內(nèi)所有非簇頭節(jié)點(diǎn)及自身的估計(jì)位置；

步驟C2：簇C_now的簇頭節(jié)點(diǎn)與鄰近簇的簇頭節(jié)點(diǎn)進(jìn)行通信，將簇C_now內(nèi)所有節(jié)點(diǎn)的估計(jì)位置發(fā)送給鄰近簇的簇頭節(jié)點(diǎn)，并將從鄰近簇的簇頭節(jié)點(diǎn)處獲得的鄰近簇內(nèi)所有節(jié)點(diǎn)的估計(jì)位置發(fā)送給簇C_now內(nèi)的邊界節(jié)點(diǎn)；

步驟C3：邊界節(jié)點(diǎn)根據(jù)接收到的鄰近簇內(nèi)所有節(jié)點(diǎn)的估計(jì)位置，通過節(jié)點(diǎn)重聚類評估方法，對當(dāng)前時(shí)刻自身是否需要進(jìn)行重聚類進(jìn)行評估，即計(jì)算自身分別與簇C_now、鄰近簇之間的從屬度；

所述節(jié)點(diǎn)重聚類評估方法，具體為：

定義節(jié)點(diǎn)i與簇C之間的從屬度ψ(i,C)計(jì)算方式為

其中，d(i,j)為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的歐氏距離，節(jié)點(diǎn)j屬于簇C；

對于每個(gè)邊界節(jié)點(diǎn)，將具有最大從屬度的簇作為當(dāng)前時(shí)刻最適合加入的簇，記為簇C_now-opt；若簇C_now-opt與簇C_now不同，則判定當(dāng)前時(shí)刻該邊界節(jié)點(diǎn)需要進(jìn)行重聚類；

移動(dòng)節(jié)點(diǎn)實(shí)現(xiàn)自身的重聚類，通過步驟D執(zhí)行重聚類過程，步驟D包括如下步驟：

步驟D1：在簇C_now中，非簇頭節(jié)點(diǎn)向簇頭節(jié)點(diǎn)發(fā)送步驟B中得到的預(yù)測位置，非簇頭節(jié)點(diǎn)中需要進(jìn)行重聚類的邊界節(jié)點(diǎn)向簇頭節(jié)點(diǎn)發(fā)送重聚類請求，重聚類請求包括目標(biāo)簇C_now-opt的信息；

步驟D2：簇C_now的簇頭節(jié)點(diǎn)將接收到的鄰近簇內(nèi)節(jié)點(diǎn)的預(yù)測位置、重聚類請求以及自身簇內(nèi)的預(yù)測位置進(jìn)行整合得到已整合信息之后，與鄰近簇的簇頭節(jié)點(diǎn)再次進(jìn)行通信，向鄰近簇的簇頭節(jié)點(diǎn)發(fā)送所述已整合信息，并將接收到的鄰近簇內(nèi)節(jié)點(diǎn)的預(yù)測位置、重聚類請求以及自身所屬簇C_now內(nèi)節(jié)點(diǎn)的預(yù)測位置、重聚類請求發(fā)送給簇C_now內(nèi)需要進(jìn)行重聚類的邊界節(jié)點(diǎn)；

步驟D3：需要進(jìn)行重聚類的邊界節(jié)點(diǎn)利用獲得的節(jié)點(diǎn)預(yù)測位置以及重聚類請求，利用所述節(jié)點(diǎn)重聚類評估方法，對下一時(shí)刻自身是否需要重聚類進(jìn)行評估，得到下一時(shí)刻最適合加入的簇C_next-opt；若C_next-opt與C_now不同，則說明該邊界節(jié)點(diǎn)的重聚類過程不存在乒乓效應(yīng)，該邊界節(jié)點(diǎn)能夠重聚類到簇C_now-opt中，進(jìn)入步驟D4繼續(xù)執(zhí)行；否則，說明當(dāng)前重聚類周期中該邊界節(jié)點(diǎn)不能進(jìn)行重聚類，則該邊界節(jié)點(diǎn)不進(jìn)行重聚類，簇C_now的簇頭節(jié)點(diǎn)將忽略該邊界節(jié)點(diǎn)之前發(fā)送的重聚類請求；

步驟D4：該邊界節(jié)點(diǎn)向簇C_now的簇頭節(jié)點(diǎn)發(fā)送重聚類確認(rèn)信息，向簇C_now-opt的簇頭節(jié)點(diǎn)發(fā)送請求加入的信息，并且在第k+1個(gè)時(shí)刻脫離簇C_now并加入簇C_now-opt。