基於樹形結構的具有可靠性保證的數據聚合方法

2023-05-15 08:56:31 1

專利名稱：基於樹形結構的具有可靠性保證的數據聚合方法
技術領域：
本發明涉及一種在無線傳感器網絡中具有可靠性保證的數據收集的方法，更特別 地說，是指一種基於樹形結構的具有可靠性保證的數據收集方法。
背景技術：
在無線傳感器網絡中，由於節點的通信能力較弱、能量有限以及外部環境的幹擾， 造成網絡動態變化快，鏈路失效、節點死亡等現象時有發生，若對網絡狀態的變化情況不加 管理很容易導致網絡性能降低以及網絡中數據的丟失，甚至造成網絡過早失效。因此，有必 要提高無線傳感器網絡數據收集的可靠性。同時無線傳感器網絡的資源有限性要求狀態信 息收集的過程快速有效，不能長期佔用網絡資源，還要保證信息收集的精確性。樹形結構是在網絡中構建一棵生成樹，該樹的根節點為數據查詢節點，其餘的節 點為這棵生成樹的枝葉節點。在一棵生成樹中，除根節點之外，每個節點有且僅有一個前 繼節點，即父節點；並且擁有0個或多個的後繼節點，即子節點；同一個節點下的所有子節 點，稱之為兄弟節點。基於樹形結構的數據聚合方法是沿著該生成樹自下而上地進行數據 聚合。即聚合的結果在樹中自下而上的逐層傳遞，每個節點首先從其子節點接收數據，然後 將聚合後的結果發送給它的父節點。採用這樣的拓撲結構進行數據的聚合，其優點在於1) 每個節點在進行數據聚合時只發送一條信息；2)每個節點在查詢時只對聚合的結果進行 一次解析。然而，沿著生成樹中進行數據聚合時，節點失效或者是傳輸失敗將會對聚合的結 果造成較大的影響。這是由於數據的擁有者和查詢者之間只存在一條路徑，並且，信息在傳 輸時使用的是節能的、不可靠的通信方法。因此，節點失效或傳輸失敗會造成整個子樹的聚 合結果丟失，不幸的是，節點失效與傳輸失敗會經常在無線傳感器網絡中發生。所以，在基 於生成樹的聚合策略中，有很大一部分的聚合結果沒有能傳達到樹的根節點上，從而導致 在數據查詢時只能得到部分節點的數據聚合的結果，因此會出現重大的錯誤。

發明內容
有鑑於此，本發明目的在於提供一種基於樹形結構的具有可靠性保證的數據聚合 方法。該方法通過生成樹建立模塊1、樹內數據聚合模塊2、數據檢測模塊3和生成樹修正 模塊4實現。生成樹建立模塊1通過廣播要查詢的節點信息，以及接收到的其他節點的廣 播信息，結合調整節點的level實現生成樹的建立；樹內數據聚合模塊2通過樹內數據聚合 方法，實現了數據的多聚合以及無損聚合；數據檢測模塊3通過基於權重的投票算法，使得 距離近的鄰居的投票具有更高的權重，從而達到有效地進行數據的異常檢測；生成樹修正 模塊4通過採用備用父節點選擇方法完成對備用父節點集合的生成與修正。在生成樹建立模塊1中採用生成樹構造方法的執行步驟有步驟101 初始化無線傳感器網絡，並將所有網絡中的各個節點的狀態設為等待 狀態，即Flag = 0 ；
步驟102 由樹根節點廣播生成樹報文 GTD {Head, ID, Level，FatherLevel，Data}， 且層數level設置為0 ；所述的 GTD{Head, ID, Level, FatherLevel, Data}中 Head 表示報文頭，ID 表示生 成樹報文的節點序號，Level表示生成樹報文的節點層數，FatherLevel表示生成樹報文的 父節點層數，Data表示報文的內容；步驟103 鄰居節點A在接收到所述的GTD報文之後，一方面將發送GTD報文的節 點B提取出來，另一方面進行自己狀態Flag判斷，若Flag = 0則轉步驟103-1 ；若Flag Φ 0 則轉步驟104 ；步驟103-1 鄰居節點A隨機從等待時間Time
中取出一個時間進行等待，同 時根據GTD報文設置自己的父節點及層數level並將自身狀態修改為待定，即Flag = 1，則 轉步驟108 ；其中，該父節點為發送GTD報文的節點記為節點B ；步驟104 判斷所述鄰居節點A的狀態Flag，是否等於1，是，則轉步驟105 ；否則， 鄰居節點A將收到的GTD報文丟棄，並轉步驟108 ；步驟105 比較鄰居節點A和節點B的level大小，若IevelA等於levelB+Ι時， 則轉步驟106 ；若IevelA不等於levelB+Ι時，鄰居節點A將收到的GTD報文丟棄，並轉步 驟108 ；鄰居節點A的層數記為levelA，節點B的層數記為IevelB ；步驟106 根據節點B的信號強度RSS來判斷鄰居節點A與節點B的距離DA_B，若 Da_b在R/2以內，並且比Da_c距離要近時，則將原父節點C修改為節點B，並將自身狀態修改 為結束，即Flag = 2，轉步驟108 ；否則，轉步驟107 ；R為鄰居節點A的感知半徑；步驟107 鄰居節點A發送調用樹信號GTS來調用生成樹修正模塊4，並將節點B 加入到備用父節點集合 FS{levelB，Aid, Bid, ListenCounts, NoListenCounts, RSS}中，並轉 步驟 108 ；所述的 FS{levelB，Aid, Bid, ListenCounts, NoListenCounts, RSS}中 IevelB 為 節點B所在的層數，Aid為節點A的序號，Bid為節點B的序號，ListenCounts為偵聽成功次 數，NoListenCounts為偵聽失敗次數，RSS為節點A在偵聽節點B時的信號強度；步驟108 若鄰居節點A的等待時間到達，則設置自己層數為levelB+Ι，並將自身 狀態修改為結束，即Flag = 2，然後用自己的level和ID替換GTD報文中的level和ID, 並將新報文廣播出去，轉步驟109 ；若鄰居節點A的等待時間未到達，轉步驟103 ；步驟109 遍歷網絡中的所有節點，並判斷所有節點的狀態是否都是「結束」，即所 有節點的狀態Flag = 2，若是，則構造樹結束，並向數據聚合模塊2發送聚合啟動信號DASS 和最大層次MaxLevel ；否則轉步驟103。在數據聚合模塊2中採用的樹內數據聚合方法的執行步驟如下步驟201 由MaxLevel層節點生成數據聚合結果DA，並設置當前level為 MaxLevel ；步驟202:鄰居節點A進入發送階段，其層數為level，並廣播自身數據聚合結果 DA ；步驟203 節點B在接收到節點A的數據聚合結果DA後，若節點A的父親節點為 節點B，則對數據聚合結果DA進行存儲；步驟204 節點B在接收到節點A的數據聚合結果DA後，若節點A的父節點與節
7點B的父節點相同，則說明節點A與節點B為兄弟節點，則對數據聚合結果DA進行緩存；其中，兄弟節點指父節點相同的節點；步驟205 若所有層數為level的節點都發送了自身的數據聚合結果，則轉步驟 206 ；未發送完成，則轉步驟202 ；步驟206 進入轉發周期，即層數為level的節點向自身父節點轉發其兄弟節點的 數據聚合結果DA，同時進入對父節點的監聽階段，若在一次數據聚合過程中一直沒有收到 父節點發送的任何的數據，發送調用樹信號DAS調用修正模塊4進行生成樹的修正，等待修 正模塊4返回備用父節點Cid，然後將該節點的父節點設置為Cid ；步驟207 父節點在收到所有子節點的數據聚合結果DA後，向數據檢測模塊3發 送數據檢測啟動指令start_2，對各個子節點發送來的數據進行檢測，並等待數據檢測模塊 3返回數據檢測結果DR，若DR = 1，則將對應的節點的數據聚合結果DA刪除；步驟208 父節點將所有子節點發來的數據進行聚合，以生成新的數據聚合結果 DA ；步驟209 若所有層數為level的節點都轉發了其兄弟節點的數據，執行level-1， 則轉步驟210 ；若轉發未完成，則轉步驟206 ；步驟210 若層數level = 0，向生成樹建立模塊1返回數據聚合結果DA，數據聚 合結束；若層數level > 0,則轉步驟202。在數據檢測模塊3中採用的讀向量檢測方法的執行步驟有步驟301 任意一父節點E在收到子節點F發送的數據聚合結果後，根據子節點F
前η次發送的數據Cli與本次收到的數據d進行比較，若
(1表示閾值)則認為
異常，並進行投票詢問，轉步驟302 ；若
，向聚合模塊2報告詢問後的結果DR，
即DR = 0，結束數據檢測；步驟302 父節點E對異常節點F廣播投票問詢報文Re questDadagram{srcid, desid, hop, data}，並設置轉發跳數 hop = 1 ；投票問詢報文RequestDadagram {srcid，desid，hop，data}中 srcid 為發起問詢節點 的節點序號，desid為異常節點的節點序號，hop為報文轉發的跳數，data為報文的內容；步驟303 鄰居節點H收到Re questDatagram報文後，從報文中提取出轉發次數 hop，若hop < 2，則用hop+Ι替換原報文中的hop，並將該報文進行轉發，轉步驟304 ；步驟304 節點F是否在鄰居節點H的感知半徑內，若在轉步驟305 ；若不在則轉步 驟 303 ；步驟305 根據異常讀向量對節點聚合結果進行異常判斷，其中讀向量bi (t) = (Xi (、)，Xi (t2)，…，Xi (tn)}，其中 Xi (tn)表示節點 i 在 tn 時刻的 讀數，η表示前η次數據；
^(0x^(0兩個鄰居節點之間的協方差關係
)表 示節點i的讀向量，bj(t)表示節點j的讀向量，節點i與節點j互為鄰居節點；
讀向量的模Il bi(t) Il2 = Xi2 U1)+Xi2U2)+. · · +Xi2(tn)；若Corri,」> θ τ，則表示節點i與節點j之間不存在差異；否則，表示節點i與節 點j之間存在著差異；θ τ表示協方差閾值，一般取0.8。步驟306 節點H根據異常判斷出的結果上傳投票結果報文Result {head，Hid，Fid， Eid, hop, RSS' }，並置hop = 1，若結果正常，則上傳的投票為正；反之為負，根據與異常節 點F的距離不同，投票的權值也不同，權值記為RSS'，即節點H在偵聽時得到的節點F信號 強度，因此離異常節點F越近的節點在投票時的權重越大；投票結果報文Result {head, Hid, Fid, Eid, hop, RSS' }中 head 為報文頭，Hid 為投 票節點的節點序號，Fid為異常節點的節點序號，Eid是發起投票問詢的節點序號，hop為報 文轉發的跳數，RSS'為投票的值；步驟307 節點D收到投票結果報文後，若節點D是發起投票問詢的節點，則將投 票結果進行緩存，轉步驟309 ；否則轉步驟308 ；步驟308 節點D收到投票結果報文後，判斷轉發跳數hop，若hop < 2，則用hop+1 替換原報文中的hop，並將該報文進行轉發；步驟309 節點E根據詢問結果判斷節點F的數據是否異常，若所有投票為正的加 權結果大於所有投票為負的加權結果，則認為節點F數據正常，即DR = 0 ；反之，若所有投 票為正的加權結果小於等於所有投票為負的加權結果，則認為節點F數據異常，即DR = 1 ；步驟310 節點E向聚合模塊2報告詢問後的結果DR，流程結束。在生成樹修正模塊4中採用的備用父節點選擇方法的執行步驟有步驟401 判斷節點A收到的信號類型，若為GTS則轉步驟402，若為DAS則轉步驟 407 ；步驟402 判斷節點B是否在備用父節點集合FS {levelB, Aid, Bid, ListenCounts， NoLi stenCounts，RSS}中，若沒有則轉步驟403，若有則轉步驟404 ；在備用父節點集合FS{levelB，Aid, Bid, ListenCounts, NoListenCounts, RSS}中 IevelB為節點B所在的層數，Aid為節點A的序號，Bid為節點B的序號，ListenCounts為偵 聽成功次數，NoListenCounts為偵聽失敗次數，RSS為節點A在偵聽節點B時的信號強度；步驟403 把節點B加入備用父節點集合FS，並設置偵聽成功次數ListenCounts =0，偵聽失敗次數NoListenCoimts = O ；向生成樹建立模塊1返回備用父節點集合FS ；步驟404 開啟查詢周期T，設置監聽狀態MonitorStatus = O ；步驟405 在查詢周期T中，若監聽到父節點信息，則修改監聽狀態MonitorStatus =1 ；步驟406 查詢周期T結束時，若MonitorStatus = 1，則偵聽成功次數加1 ；若 MonitorStatus = 0，則偵聽失敗次數加1 ；步驟407 遍歷備用父節點集合FS，選擇ListenCounts/NoListenCounts最大的節 點加入臨時父節點集合TempFathers ；步驟408 從臨時父節點集合TempFathers中選擇RSS最大的節點作為新的父節 點Cid ；並結束生成樹修正模塊4向數據聚合模塊2返回備用父節點。本發明數據聚合方法的優點在於(1)通過樹形結構有效的延長了整個無線傳感器網絡的使用壽命，並且提高了網絡的可靠性。(2)由於採用了樹形結構，從而解決了熱點問題(熱點問題是指無線傳感器網絡 中某些節點由於擔負的通信量過大，以至於該節點的能量過早的消耗殆盡，從而引起整個 網絡性能下降的現象。)，提高了整個網絡的生存時間。(3)由於採用樹形結構實現了數據的多聚合以及無損聚合，提高了數據傳輸成功 率，減小了傳輸數據量。(4)在數據檢測模塊中採用了基於權重的投票算法，從而有效地平衡網絡的可靠 性與能耗關係。(5)在數據檢測模塊中採用了異常讀向量來進行數據的異常檢測，從而提高了數 據檢測的正確率。(6)在生成樹修正模塊中應用備用父節點集合的方法，對生成樹進行了修正，從而 保證了網絡通信的可靠性和數據聚合的準確性。


圖1是本發明基於樹形結構的具有可靠性保證的數據聚合方法的結構框圖。
具體實施例方式本發明是一種基於樹形結構的具有可靠性保證的數據聚合方法，該數據聚合方法 通過四個模塊(生成樹建立模塊1、樹內數據聚合模塊2、數據檢測模塊3和生成樹修正模 塊4)實現，在每個模塊中依據了不同的方法進行處理，從而實現了整個網絡中數據的快 速、高效聚合。在本發明中，生成樹建立模塊1採用生成樹構造方法完成整個網絡樹形結構 的建立；數據聚合模塊2採用樹內數據聚合方法完成聚合結果的生成；數據檢測模塊3採 用讀向量的檢測方法完成對節點失效的檢測；生成樹修正模塊4採用備用父節點選擇方法 完成對備用父節點集合的生成與修正。生成樹建立模塊1完成的三個任務第一方面生成樹建立模塊1根據啟動指令start_l調用生成樹構造方法完成整 個網絡樹形結構的建立；第二方面生成樹建立模塊1向數據聚合模塊2發送聚合啟動信號DASS以及最大 層次MaxLevel，並接收由數據聚合模塊2返回的聚合數據結果DA ；第三方面生成樹建立模塊1向生成樹修正模塊4發送調用樹信號GTS，並接收由 生成樹修正模塊4返回的備用父節點集合FS ；在生成樹建立模塊1中採用生成樹構造方法的執行步驟有步驟101 初始化無線傳感器網絡，並將所有網絡中的各個節點的狀態設為等待 狀態，即Flag = 0 ；步驟102 由樹根節點廣播生成樹報文 GTD {Head，ID, Level, FatherLevel, Data}， 且層數level設置為0 ；步驟103 鄰居節點A在接收到所述的GTD報文之後，一方面將發送GTD報文的節 點B提取出來，另一方面進行自己狀態Flag判斷，若Flag = 0則轉步驟103-1 ；若Flag Φ 0 則轉步驟104 ；
步驟103-1 鄰居節點A隨機從等待時間Time
(t表示最長的等待時間，一般 可以設置為2秒)中取出一個時間進行等待，同時根據GTD報文設置自己的父節點及層數 level並將自身狀態修改為待定，即Flag = 1，則轉步驟108 ；其中，該父節點為發送GTD報 文的節點記為節點B;步驟104 判斷所述鄰居節點A的狀態Flag，是否等於1，是，則轉步驟105 ；否則， 鄰居節點A將收到的GTD報文丟棄，並轉步驟108 ；步驟105 比較鄰居節點A和節點B的level大小，若IevelA等於levelB+Ι時， 則轉步驟106 ；若IevelA不等於levelB+Ι時，鄰居節點A將收到的GTD報文丟棄，並轉步 驟 108 ；在本發明中，鄰居節點A的層數記為levelA，節點B的層數記為IevelB ；步驟106 根據節點B的信號強度RSS來判斷鄰居節點A與節點B的距離DA_B，若 Da_b在R/2以內，並且比Da_c距離要近時，則將原父節點C修改為節點B，並將自身狀態修改 為結束，即Flag = 2，轉步驟108 ；否則，轉步驟107 ；在本發明中，原父節點C是指鄰居節點A的初始父節點；鄰居節點A與原父節點C 的距離記為Da_。；R為鄰居節點A的感知半徑；步驟107 鄰居節點A發送調用樹信號GTS來調用生成樹修正模塊4，並將節點B 加入到備用父節點集合 FS{levelB，Aid, Bid, ListenCounts, NoListenCounts, RSS}中，並轉 步驟108 ；步驟108 若鄰居節點A的等待時間到達，則設置自己層數為levelB+Ι，並將自身 狀態修改為結束，即Flag = 2，然後用自己的level和ID替換GTD報文中的level和ID, 並將新報文廣播出去，轉步驟109 ；若鄰居節點A的等待時間未到達，轉步驟103 ；步驟109 遍歷網絡中的所有節點，並判斷所有節點的狀態是否都是「結束」，即所 有節點的狀態Flag = 2，若是，則構造樹結束，並向數據聚合模塊2發送聚合啟動信號DASS 和最大層次MaxLevel ；否則轉步驟103。在本發明中，所述的GTD {Head，ID, Level, FatherLevel，Data}中 Head 表示報文 頭，ID表示生成樹報文的節點序號，Level表示生成樹報文的節點層數，FatherLevel表示 生成樹報文的父節點層數，Data表示報文的內容。在本發明中，所述的FSllevelB, Aid, Bid, ListenCounts, NoListenCounts, RSS}中 IevelB為節點B所在的層數，Aid為節點A的序號，Bid為節點B的序號，ListenCoimts為偵 聽成功次數，NoListenCounts為偵聽失敗次數，RSS為節點A在偵聽節點B時的信號強度。數據聚合模塊2完成的三個任務第一方面數據聚合模塊2根據接收到的生成樹建立模塊1發送的聚合啟動信號 DASS以及最大層次MaxLevel，調用樹內數據聚合方法完成數據的聚合，並向生成樹建立模 塊1返回數據聚合結果DA;第二方面數據聚合模塊2向生成樹修正模塊4發送調用樹信號DAS，並接收生成 樹修正模塊4返回的備用父節點Cid ；第三方面數據聚合模塊2向數據檢測模塊3發送數據檢測啟動指令start_2，並 接收數據檢測模塊3返回的數據檢測結果DR ；
在數據聚合模塊2中採用的樹內數據聚合方法的執行步驟如下步驟201 由MaxLevel層節點生成數據聚合結果DA，並設置當前level為 MaxLevel ；步驟202:鄰居節點A進入發送階段，其層數為level，並廣播自身數據聚合結果 DA ；步驟203 節點B在接收到節點A的數據聚合結果DA後，若節點A的父親節點為 節點B，則對數據聚合結果DA進行存儲；步驟204 節點B在接收到節點A的數據聚合結果DA後，若節點A的父節點與節 點B的父節點相同，則說明節點A與節點B為兄弟節點，則對數據聚合結果DA進行緩存；其中，兄弟節點指父節點相同的節點；步驟205 若所有層數為level的節點都發送了自身的數據聚合結果，則轉步驟 206 ；未發送完成，則轉步驟202 ；步驟206 進入轉發周期，即層數為level的節點向自身父節點轉發其兄弟節點的 數據聚合結果DA，同時進入對父節點的監聽階段，若在一次數據聚合過程中一直沒有收到 父節點發送的任何的數據，發送調用樹信號DAS調用修正模塊4進行生成樹的修正，等待修 正模塊4返回備用父節點Cid，然後將該節點的父節點設置為Cid ；步驟207 父節點在收到所有子節點的數據聚合結果DA後，向數據檢測模塊3發 送數據檢測啟動指令start_2，對各個子節點發送來的數據進行檢測，並等待數據檢測模塊 3返回數據檢測結果DR，若DR = 1 (數據檢測結果異常)，則將對應的節點的數據聚合結果 DA刪除；步驟208 父節點將所有子節點發來的數據進行聚合，以生成新的數據聚合結果 DA ；步驟209:若所有層數為level的節點都轉發了其兄弟節點的數據，執行level-1， 則轉步驟210 ；若轉發未完成，則轉步驟206 ；步驟210 若層數level = 0，向生成樹建立模塊1返回數據聚合結果DA，數據聚 合結束；若層數level > 0,則轉步驟202。數據檢測模塊3完成的一個任務數據檢測模塊3根據數據聚合模塊2發送的數據檢測啟動指令start_2調用讀向 量檢測方法完成整個數據的檢測，並向數據聚合模塊2返回數據檢測結果DR ；在數據檢測模塊3中採用的讀向量檢測方法的執行步驟有步驟301 任意一父節點E在收到子節點F發送的數據聚合結果後，根據子節點F
前η次發送的數據Cli與本次收到的數據d進行比較，若
；成^Z則認為異常，並進行
投票詢問，轉步驟302 ；若
,向聚合模塊2報告詢問後的結果DR，即DR = 0，結 束數據檢測；在本發明中，1表示閾值，若在測量溫度的條件下，閾值一般設定為5°C 10°C ；若 在測量速度的條件下，閾值一般設定為lOm/s。步驟302 父節點E對異常節點F廣播投票問詢報文Re questDadagram{srcid,desid, hop, data}，並設置轉發跳數 hop = 1 ；投票問詢報文RequestDadagram{srcid，desid，hop，data}中 srcid*發起問詢節點 的節點序號，desid為異常節點的節點序號，hop為報文轉發的跳數，data為報文的內容。步驟303 鄰居節點H收到Re questDatagram報文後，從報文中提取出轉發次數 hop，若hop < 2，則用hop+Ι替換原報文中的hop，並將該報文進行轉發，轉步驟304 ；步驟304 節點F是否在鄰居節點H的感知半徑內，若在轉步驟305 ；若不在則轉步 驟 303 ；步驟305 根據異常讀向量對節點聚合結果進行異常判斷，其中讀向量b「t) = (XiUHa2),... ,Xi (tn)}，其中 Xi (tn)表示節點 士在、時刻的 讀數，η表示前η次數據；兩個鄰居節點之間的協方差關係= |k "、丨丨2 ||· . . ||2 『A "、，Mt)表
示節點i的讀向量，bj(t)表示節點j的讀向量，節點i與節點j互為鄰居節點；讀向量的模IIbiU) Il2 = Xi2U1)+Xi2U2)+...+Xi2Un)；若Corri,」> θ τ，則表示節點i與節點j之間不存在差異；否則，表示節點i與節 點j之間存在著差異；θ τ表示協方差閾值，一般取0.8。步驟306 節點H根據異常判斷出的結果上傳投票結果報文Result {head, Hid, Fid, Eid, hop, RSS' }，並置hop = 1，若結果正常，則上傳的投票為正；反之為負，根據與異常節 點F的距離不同，投票的權值也不同，權值記為RSS'，即節點H在偵聽時得到的節點F信號 強度，因此離異常節點F越近的節點在投票時的權重越大；投票結果報文Result {head，Hid，Fid，Eid，hop，RSS' }中 head 為報文頭，Hid 為投 票節點的節點序號，Fid為異常節點的節點序號，Eid是發起投票問詢的節點序號，hop為報 文轉發的跳數，RSS'為投票的值。步驟307 節點D收到投票結果報文後，若節點D是發起投票問詢的節點，則將投 票結果進行緩存，轉步驟309 ；否則轉步驟308 ；步驟308 節點D收到投票結果報文後，判斷轉發跳數hop，若hop < 2，則用hop+1 替換原報文中的hop，並將該報文進行轉發；步驟309 節點E根據詢問結果判斷節點F的數據是否異常，若所有投票為正的加 權結果大於所有投票為負的加權結果，則認為節點F數據正常，即DR = 0 ；反之，若所有投 票為正的加權結果小於等於所有投票為負的加權結果，則認為節點F數據異常，即DR = 1。步驟310 節點E向聚合模塊2報告詢問後的結果DR，流程結束。生成樹修正模塊4完成的兩個任務第一方面生成樹修正模塊4根據接收到的生成樹建立模塊1發送的調用樹信號 GTS調用備用父節點選擇方法完成生成樹修正過程，並向生成樹建立模塊1返回備用父節 點集合 FS {levelB，Aid, Bid, ListenCounts，NoListenCounts，RSS}；第二方面生成樹修正模塊4根據接收到的數據聚合模塊2發送的調用樹信號 DAS調用備用父節點選擇方法完成生成樹修正過程，並向數據聚合模塊2返回備用父節點 Cid ；在生成樹修正模塊4中採用的備用父節點選擇方法的執行步驟有
13
步驟401 判斷節點A收到的信號類型，若為GTS則轉步驟402，若為DAS則轉步驟 407 ；步驟402 判斷節點B是否在備用父節點集合FS{levelB，Aid，Bid, ListenCounts， NoListenCounts，RSS}中，若沒有則轉步驟403，若有則轉步驟404 ；在備用父節點集合FS{levelB，Aid, Bid, ListenCounts, NoListenCounts, RSS}中 levelB為節點B所在的層數，Aid為節點A的序號，Bid為節點B的序號，ListenCounts為偵 聽成功次數，NoListenCounts為偵聽失敗次數，RSS為節點A在偵聽節點B時的信號強度。步驟403 把節點B加入備用父節點集合FS，並設置偵聽成功次數ListenCounts =0，偵聽失敗次數NoListenCounts = 0 ；向生成樹建立模塊1返回備用父節點集合FS ；步驟404 開啟查詢周期T，設置監聽狀態MonitorStatus = 0 ；步驟405 在查詢周期T中，若監聽到父節點信息，則修改監聽狀態MonitorStatus =1 ；步驟406 查詢周期T結束時，若MonitorStatus = 1，則偵聽成功次數加1 ；若 MonitorStatus = 0，則偵聽失敗次數加1 ；步驟407 遍歷備用父節點集合FS，選擇ListenCounts/NoListenCounts最大的節 點加入臨時父節點集合TempFathers ；步驟408 從臨時父節點集合TempFathers中選擇RSS最大的節點作為新的父節 點Cid ；並結束生成樹修正模塊4向數據聚合模塊2返回備用父節點。本發明鑑於樹形結構能夠實現網絡中數據的快速聚合，使系統能夠方便地進行數 據的查找和使用，並且減少整個系統在數據聚合過程中的通信量，從而延長系統的使用壽 命。此外，樹形結構具有一定的容錯能力，即當部分節點死亡時，能夠迅速的自我修復，從而 提高系統的可靠性。本發明通過樹形結構的建立延長了系統使用壽命，解決了熱點問題，提高了系統 的可靠性；同時基於樹內數據聚合的方法實現了數據的多聚合以及無損聚合，同時在減少 了傳輸數據量的前提下提高了傳輸成功率；採用基於權重的投票方法，同時提出了異常讀 向量，有效地進行了數據的異常檢測，保證了數據收集的可靠性；除此之外，提出了使用備 用父節點集合的方法，對生成樹進行了修正，從而保證了網絡通信的可靠性和數據聚合的 準確性。
權利要求
一種基於樹形結構的具有可靠性保證的數據聚合方法，其特徵在於該數據聚合方法通過生成樹建立模塊(1)、樹內數據聚合模塊(2)、數據檢測模塊(3)和生成樹修正模塊(4)實現，在每個模塊中依據了不同的方法進行處理，從而實現了整個網絡中數據的聚合；生成樹建立模塊(1)採用生成樹構造方法完成整個網絡樹形結構的建立；數據聚合模塊(2)採用樹內數據聚合方法完成聚合結果的生成；數據檢測模塊(3)採用讀向量的檢測方法完成對節點失效的檢測；生成樹修正模塊(4)採用備用父節點選擇方法完成對備用父節點集合的生成與修正。
2.根據權利要求1所述的基於樹形結構的具有可靠性保證的數據聚合方法，其特徵在 於在生成樹建立模塊(1)中採用生成樹構造方法的執行步驟有步驟101 初始化無線傳感器網絡，並將所有網絡中的各個節點的狀態設為等待狀態， 即 Flag = 0 ；步驟102 由樹根節點廣播生成樹報文GTD {Head，ID，Level，FatherLevel，Data}，且層 數level設置為0 ；所述的GTD{Head，ID, Level, FatherLevel，Data}中Head表示報文頭，ID表示生成樹 報文的節點序號，Level表示生成樹報文的節點層數，FatherLevel表示生成樹報文的父節 點層數，Data表示報文的內容；步驟103 鄰居節點A在接收到所述的GTD報文之後，一方面將發送GTD報文的節點B 提取出來，另一方面進行自己狀態Flag判斷，若Flag = 0則轉步驟103-1 ；若Flag Φ 0則 轉步驟104 ；步驟103-1 鄰居節點A隨機從等待時間Time
中取出一個時間進行等待，同時根 據GTD報文設置自己的父節點及層數level並將自身狀態修改為待定，即Flag = 1，則轉步 驟108 ；其中，該父節點為發送GTD報文的節點記為節點B ；步驟104 判斷所述鄰居節點A的狀態Flag，是否等於1，是，則轉步驟105 ；否則，鄰居 節點A將收到的GTD報文丟棄，並轉步驟108 ；步驟105 比較鄰居節點A和節點B的level大小，若IevelA等於levelB+Ι時，則轉步 驟106 ；若IevelA不等於levelB+Ι時，鄰居節點A將收到的GTD報文丟棄，並轉步驟108 ； 鄰居節點A的層數記為levelA，節點B的層數記為IevelB ；步驟106 根據節點B的信號強度RSS來判斷鄰居節點A與節點B的距離DA_B，若DA_B 在R/2以內，並且比Da_c距離要近時，則將原父節點C修改為節點B，並將自身狀態修改為結 束，即Flag = 2，轉步驟108 ；否則，轉步驟107 ；R為鄰居節點A的感知半徑；步驟107 鄰居節點A發送調用樹信號GTS來調用生成樹修正模塊4，並將節點B加入 到備用父節點集合 FS{levelB，Aid, Bid, ListenCounts, NoListenCounts, RSS}中，並轉步驟 108 ；Ijf^ FSllevelB, Aid，Bid, ListenCounts, NoListenCounts, RSS}中 IevelB ^Ji ^ B所在的層數，Aid為節點A的序號，Bid為節點B的序號，ListenCounts為偵聽成功次數， NoListenCounts為偵聽失敗次數，RSS為節點A在偵聽節點B時的信號強度；步驟108:若鄰居節點A的等待時間到達，則設置自己層數為levelB+Ι，並將自身狀態 修改為結束，即Flag = 2，然後用自己的level和ID替換GTD報文中的level和ID，並將 新報文廣播出去，轉步驟109;若鄰居節點A的等待時間未到達，轉步驟103 ；步驟109 遍歷網絡中的所有節點，並判斷所有節點的狀態是否都是「結束」，即所有節 點的狀態Flag = 2，若是，則構造樹結束，並向數據聚合模塊2發送聚合啟動信號DASS和最 大層次MaxLevel ；否則轉步驟103。
3.根據權利要求1所述的基於樹形結構的具有可靠性保證的數據聚合方法，其特徵 在於在數據聚合模塊2中採用的樹內數據聚合方法的執行步驟如下步驟201 由MaxLevel層節點生成數據聚合結果DA，並設置當前level為MaxLevel ； 步驟202 鄰居節點A進入發送階段，其層數為level，並廣播自身數據聚合結果DA ； 步驟203 節點B在接收到節點A的數據聚合結果DA後，若節點A的父親節點為節點 B，則對數據聚合結果DA進行存儲；步驟204 節點B在接收到節點A的數據聚合結果DA後，若節點A的父節點與節點B的 父節點相同，則說明節點A與節點B為兄弟節點，則對數據聚合結果DA進行緩存； 其中，兄弟節點指父節點相同的節點；步驟205 若所有層數為level的節點都發送了自身的數據聚合結果，則轉步驟206 ； 未發送完成，則轉步驟202;步驟206 進入轉發周期，即層數為level的節點向自身父節點轉發其兄弟節點的數據 聚合結果DA，同時進入對父節點的監聽階段，若在一次數據聚合過程中一直沒有收到父節 點發送的任何的數據，發送調用樹信號DAS調用修正模塊4進行生成樹的修正，等待修正模 塊4返回備用父節點Cid，然後將該節點的父節點設置為Cid ；步驟207 父節點在收到所有子節點的數據聚合結果DA後，向數據檢測模塊3發送數 據檢測啟動指令start_2，對各個子節點發送來的數據進行檢測，並等待數據檢測模塊3返 回數據檢測結果DR，若DR = 1，則將對應的節點的數據聚合結果DA刪除；步驟208 父節點將所有子節點發來的數據進行聚合，以生成新的數據聚合結果DA ； 步驟209:若所有層數為level的節點都轉發了其兄弟節點的數據，執行level-Ι，則轉 步驟210 ；若轉發未完成，則轉步驟206 ；步驟210 若層數level = 0，向生成樹建立模塊1返回數據聚合結果DA，數據聚合結 束；若層數level > 0,則轉步驟202。
4.根據權利要求1所述的基於樹形結構的具有可靠性保證的數據聚合方法，其特徵 在於在數據檢測模塊3中採用的讀向量檢測方法的執行步驟有步驟301 任意一父節點E在收到子節點F發送的數據聚合結果後，根據子節點F前η次發送的數據Cii與本次收到的數據d進行比較，若>1 (1表示閾值)則認為異 常，並進行投票詢問，轉步驟302 ；若<1 ,向聚合模塊2報告詢問後的結果DR，即 DR = 0，結束數據檢測；步驟302 父節點E對異常節點F廣播投票問詢報文Re questDadagram{srcid, desid, hop, data}，並設置轉發跳數hop = 1 ；投票問詢 艮文 RequestDadagram{srcid，desid，hop，data}中 srcid 為發起問詢節點的節 點序號，desid為異常節點的節點序號，hop為報文轉發的跳數，data為報文的內容；步驟303 鄰居節點H收到Re questDatagram報文後，從報文中提取出轉發次數hop，若hop < 2，則用hop+Ι替換原報文中的hop，並將該報文進行轉發，轉步驟304 ；步驟304 節點F是否在鄰居節點H的感知半徑內，若在轉步驟305 ；若不在則轉步驟`303 ；步驟305 根據異常讀向量對節點聚合結果進行異常判斷，其中 讀向量b「t) = {&(、)，&(、)，...，Xi (tn)}，其中Xi (tn)表示節點1在&時刻的讀數， η表示前η次數據；b,{t)^bj{t) 磁居節點之間的協、方差關係〒穌節點i的讀向量，bj(t)表示節點j的讀向量，節點i與節點j互為鄰居節點； 讀向量的模 Il Mt) Il2 = Xi2U1)+Xi2U2)+...+Xi2Un)；若Corri, j > θ τ，則表示節點i與節點j之間不存在差異；否則，表示節點i與節點j 之間存在著差異；θ τ表示協方差閾值，一般取0.8。步驟306 節點H根據異常判斷出的結果上傳投票結果報文Result {head，Hid, Fid, Eid, hop, RSS' }，並置hop = 1，若結果正常，則上傳的投票為正；反之為負，根據與異常節點F 的距離不同，投票的權值也不同，權值記為RSS'，即節點H在偵聽時得到的節點F信號強 度，因此離異常節點F越近的節點在投票時的權重越大；投票結果報文Result {head, Hid, Fid, Eid, hop, RSS' }中head為報文頭，Hid為投票節 點的節點序號，Fid為異常節點的節點序號，Eid是發起投票問詢的節點序號，hop為報文轉 發的跳數，RSS'為投票的值；步驟307 節點D收到投票結果報文後，若節點D是發起投票問詢的節點，則將投票結 果進行緩存，轉步驟309 ；否則轉步驟308 ；步驟308 節點D收到投票結果報文後，判斷轉發跳數hop，若hop < 2，則用hop+Ι替 換原報文中的hop，並將該報文進行轉發；步驟309 節點E根據詢問結果判斷節點F的數據是否異常，若所有投票為正的加權結 果大於所有投票為負的加權結果，則認為節點F數據正常，即DR = 0 ；反之，若所有投票為 正的加權結果小於等於所有投票為負的加權結果，則認為節點F數據異常，即DR = 1 ； 步驟310 節點E向聚合模塊2報告詢問後的結果DR，流程結束。
5.根據權利要求1所述的基於樹形結構的具有可靠性保證的數據聚合方法，其特徵 在於在生成樹修正模塊4中採用的備用父節點選擇方法的執行步驟有 步驟401 判斷節點A收到的信號類型，若為GTS則轉步驟402，若為DAS則轉步驟407 ； 步驟402:判斷節點B是否在備用父節點集合FS{levelB，Aid, Bid, ListenCounts, NoLi stenCounts，RSS}中，若沒有則轉步驟403，若有則轉步驟404 ；在備用父節點集合FS{levelB，Aid，Bid,ListenCounts,NoListenCounts,RSS}中 IevelB 為節點B所在的層數，Aid為節點A的序號，Bid為節點B的序號，ListenCounts為偵聽成功 次數，NoListenCounts為偵聽失敗次數，RSS為節點A在偵聽節點B時的信號強度；步驟403 把節點B加入備用父節點集合FS，並設置偵聽成功次數ListenCoimts = 0， 偵聽失敗次數NoListenCoimts = 0 ；向生成樹建立模塊1返回備用父節點集合FS ； 步驟404 開啟查詢周期T，設置監聽狀態MonitorStatus = O ； 步驟405 在查詢周期T中，若監聽到父節點信息，則修改監聽狀態MonitorStatus =`1 ；步驟406 查詢周期T結束時，若MonitorStatus = 1，則偵聽成功次數加1 ；若 MonitorStatus = 0，則偵聽失敗次數加1 ；步驟407 遍歷備用父節點集合FS，選擇ListenCounts/NoListenCounts最大的節點加 入臨時父節點集合TempFathers ；步驟408 從臨時父節點集合TempFathers中選擇RSS最大的節點作為新的父節點Cid; 並結束生成樹修正模塊4向數據聚合模塊2返回備用父節點。
全文摘要
本發明公開了一種基於樹形結構的具有可靠性保證的數據聚合方法，該聚合方法包括有生成樹建立模塊、樹內數據聚合模塊、數據檢測模塊和生成樹修正模塊。該聚合方法通過使用樹形結構來實現網絡中數據的快速聚合，使整個網絡能夠方便地進行數據的查找和使用，並且減少整個網絡在數據聚合過程中的通信量，從而延長整個網絡的使用壽命；同時採用了數據檢測以及生成樹修正的方法，實現了對節點損壞及節點死亡等現象的監測與發現，從而提高了網絡中數據傳輸的準確性和有效性，增加了整個網絡的可靠性。
文檔編號H04L12/56GK101895419SQ20101022433
公開日2010年11月24日 申請日期2010年7月13日 優先權日2010年7月13日
發明者劉國師, 唐曉嵐, 熊璋, 羅亞萍, 蒲菊華, 陳佳 申請人:北京航空航天大學