[發(fā)明專利]一種基于最小生成樹的數(shù)據(jù)聚合方法

有效

• 申請?zhí)枺?/td>: 201310380204.8
• 申請日: 2013-08-28
• 公開（公告）號: CN103414786A
• 公開（公告）日: 2013-11-27
• 發(fā)明（設(shè)計）人: 羅俊海;蔡濟楊;倪靜;李濤
• 申請（專利權(quán)）人: 電子科技大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04W84/18
• 代理公司: 成都宏順專利代理事務(wù)所(普通合伙) 51227
• 代理人: 周永宏

1.一種基于最小生成樹的數(shù)據(jù)聚合方法，其特征在于，具體包括：

步驟1、部署無線傳感器：在檢測區(qū)域內(nèi)，將無線傳感器部署在檢測區(qū)域；

步驟2、選擇簇頭：將整個檢測區(qū)域按網(wǎng)格進行均勻劃分，使每個網(wǎng)格的大小形狀相同，在每個網(wǎng)格中選擇位置距離網(wǎng)格中心最近的傳感器節(jié)點作為簇頭；

步驟3、分簇：簇頭選擇完成后，簇頭廣播Cluster{ID，N，Hop}信息，其中，ID為節(jié)點的編號，N為Cluster信息轉(zhuǎn)發(fā)的跳數(shù)，且N的初值為0，Hop為系統(tǒng)設(shè)定的跳數(shù)；處于簇頭附近的鄰居節(jié)點收到Cluster信息后N增加1再轉(zhuǎn)發(fā)這一信息，直到N=Hop就不再轉(zhuǎn)發(fā)Cluster信息；簇頭的鄰居節(jié)點轉(zhuǎn)發(fā)Cluster信息后再向?qū)luster信息轉(zhuǎn)發(fā)給自己的鄰居節(jié)點，然后發(fā)送一個反饋信息Join{ID，N，E_ir，d_ij，k_i}給將Cluster信息轉(zhuǎn)發(fā)給自己的節(jié)點，最終將Join信息轉(zhuǎn)發(fā)給簇頭表示自己加入該簇，其中，E_ir表示該節(jié)點此時的剩余能量，d_ij表示兩節(jié)點間的距離，k_i表示該節(jié)點能夠監(jiān)測得到的數(shù)據(jù)包的大小；如果一個節(jié)點收到了多個Cluster信息，節(jié)點就選擇N值小的加入該簇，若N相等節(jié)點就隨便選擇一個簇并加入到該簇；如果節(jié)點沒有收到Cluster信息，則節(jié)點發(fā)送Help信息，加入離自己最近的一個簇；

步驟4、簇內(nèi)節(jié)點構(gòu)成簡單圖模型：通過步驟3得到簇內(nèi)所有節(jié)點在簇內(nèi)所處的位置，將每個節(jié)點當做圖的一個頂點，每兩個相鄰節(jié)點間用邊相連接；

步驟5、簇內(nèi)權(quán)值的計算：通過所述步驟3，簇頭獲取簇內(nèi)成員節(jié)點的E_ir、d_ij和k_i，計算相鄰兩節(jié)點i，j之間的權(quán)值，權(quán)值的計算公式為：

W_ij=a₁(E_ir+E_jr)+a₂d_ij+a₃(k_i+k_j)????（1）

其中，E_jr、k_j分別表示節(jié)點j的剩余能量和節(jié)點j能夠監(jiān)測得的數(shù)據(jù)的大小，且a₁+a₂+a₃=1；

步驟6、簇內(nèi)節(jié)點構(gòu)建最小生成樹：根據(jù)所述步驟4得到的簇內(nèi)節(jié)點構(gòu)成的簡單圖模型和所述步驟5得到的權(quán)值，構(gòu)建簇內(nèi)節(jié)點最小生成樹；

步驟7、簇內(nèi)數(shù)據(jù)聚合：簇內(nèi)節(jié)點的最小生成樹構(gòu)造完成后，傳感器節(jié)點開始正常工作，從最低一級傳感器節(jié)點開始，將收集的數(shù)據(jù)傳給父節(jié)點，父節(jié)點將自己收集的數(shù)據(jù)和子節(jié)點傳來的數(shù)據(jù)聚合后再傳給自己的父節(jié)點，最終將聚合數(shù)據(jù)傳輸給簇頭；

步驟8、簇頭權(quán)值的計算：通過步驟3分簇完成后，簇頭獲得整個簇內(nèi)節(jié)點的位置、節(jié)點剩余能量和傳感器節(jié)點可能監(jiān)測得到數(shù)據(jù)的大小信息，其中，E_cir=E_1r+E_2r+…+E_ir表示整個簇的剩余能量值，K_ci表示簇頭聚合的數(shù)據(jù)大小，D_ij表示相鄰簇頭間的距離，對相鄰兩簇頭i，j之間權(quán)值進行計算，權(quán)值定義為：

W_ij=b₁(E_cir+E_cjr)+b₂D_ij+b₃(K_ci+K_cj)????（2）

其中，E_cjr和K_cj分別表示簇頭j的剩余能量值和簇頭j聚合的數(shù)據(jù)大小，且b₁+b₂+b₃=1；

步驟9、簇頭節(jié)點構(gòu)成簡單圖模型：將每個簇頭當做圖的一個頂點，相鄰簇頭之間用邊相連接，每條邊的權(quán)值由公式（2）計算得到；

步驟10、簇頭節(jié)點構(gòu)建最小生成樹：由步驟8給出的簇頭節(jié)點構(gòu)成的簡單圖模型后，構(gòu)建簇頭節(jié)點最小生成樹；

步驟11、簇頭數(shù)據(jù)聚合：簇頭節(jié)點的最小生成樹構(gòu)造完成后，從最低一級簇頭開始，將收集的數(shù)據(jù)傳給父節(jié)點，父節(jié)點將自己聚合的數(shù)據(jù)和子節(jié)點傳來的數(shù)據(jù)聚合后再傳給自己的父節(jié)點，最終將聚合數(shù)據(jù)傳輸給基站；

步驟12、均衡節(jié)點能耗：根據(jù)預(yù)先設(shè)定的輪數(shù)閾值M，每進行M輪后，重新選擇簇頭，然后重新進行步驟2-11，其中，節(jié)點的能耗可由LEACH能耗模型進行估算；

步驟13、簇的維持：簇內(nèi)節(jié)點死亡后，就可能會造成簇內(nèi)的最小生成樹路徑失效，所以在節(jié)點即將死亡前，節(jié)點發(fā)送一個Die信息給簇頭，表示自己即將死亡，簇頭接收這一信息后，簇頭就開始對簇內(nèi)節(jié)點重新構(gòu)建最小生成樹。