基於多重數據收集二叉樹的無線傳感網數據收集方法

2023-05-05 17:50:26

基於多重數據收集二叉樹的無線傳感網數據收集方法
【專利摘要】本發明提供一種基於多重二叉樹的無線傳感網數據收集方法，在隨機部署的無線傳感網中，首先將網絡中最為接近的若干節點組織成一個區域，並在每個區域中擇優選取節點，分別構建到達基站的多個備選數據收集二叉樹，較好地適應了網絡的動態變化，增強了數據收集的魯棒性；隨後，本發明實現了基於節點數的時間片輪轉數據收集機制，有效降低了數據收集過程中的衝突發生率，提升了數據收集效率；最後，本發明同時還採用了周期性重構數據收集樹的策略，有效提升了網絡的適應性。
【專利說明】基於多重數據收集二叉樹的無線傳感網數據收集方法

【技術領域】
[0001]本發明涉及一種無線傳感網高效的樹狀數據收集方法，屬於計算機網絡與無線通信技術的交叉領域。

【背景技術】
[0002]在科學技術飛速發展的今天，具有智能感知、自主組網、多跳傳輸能力的無線傳感網(Wireless Sensor Networks,WSN)技術,逐漸成為國內外科技界研究的熱點。作為計算機技術、無線通信技術、嵌入式設計技術、微電子技術等多學科的交叉技術，無線傳感網技術不僅拓展了人們獲取信息的能力和手段，更為重要的是，它將客觀世界的物理信息同傳輸網絡緊密連接在了一起，為人們的生產生活提供了極為豐富的有益信息，大大提升了人們的生活質量和工作效率。
[0003]另一方面，隨著大數據理論和技術的發展，「數據收集」問題逐漸引起了人們的重視。如何利用現有的各類感知設備，高效率、高可靠、綠色節能地收集海量的、多樣化的感知數據，正在稱為制約無線傳感網技術發展和應用最為關鍵和核心的技術之一。
[0004]然而，當前無線傳感網面臨著網絡不穩定、拓撲結構易變化、節點位置信息缺乏、通信質量差、節點能耗較高等問題。這些問題直接或間接地導致了網絡整體數據收集效率的低下，並造成了諸如數據完整性缺失、數據丟包率居高不下、數據收集路徑魯棒性較差及數據收集結構無法適應網絡的動態變化等問題，嚴重影響了基於數據內容的信息提取和決策。
[0005]眾所周知，無線傳感網已經並將繼續擁有廣闊的應用場景，在軍事國防、工農業控制、城市管理、生物醫療、環境監測、搶險救災、智能家居、智能電網等眾多領域，有足夠的用武之地。而上述應用場景和應用領域中，需要考慮的首要問題，無一例外，都將是數據收集問題。因此，本發明對於無線傳感網應用的有效開展，具有十分積極的意義。


【發明內容】

[0006]鑑於此，本發明提出一種基於多重二叉樹的無線傳感網數據收集方法，將簇狀區域劃分方法與樹狀路徑傳輸方法相結合，構造多棵備選數據收集二叉樹，並在此基礎上，實現基於數據收集量的時間片輪轉數據收集方法。該發明通過多重數據收集二叉樹的構建，可提升網絡的健壯性，降低數據包丟包率，同時，也能夠較好地適應網絡的動態變化，如節點的失效、節點的加入等，實現高效數據收集。
[0007]該種基於多重二叉樹的無線傳感網數據收集方法，在隨機部署的無線傳感網中，首先將網絡中最為接近的若干節點組織成一個區域，並在每個區域中擇優選取節點，分別構建到達基站的多個備選數據收集二叉樹，較好地適應了網絡的動態變化，增強了數據收集的魯棒性；隨後，本發明實現了基於節點數的時間片輪轉數據收集機制，有效降低了數據收集過程中的衝突發生率，提升了數據收集效率；最後，本發明同時還採用了周期性重構數據收集樹的策略，有效提升了網絡的適應性。
[0008]本發明的技術解決方案是:
[0009]一種基於多重數據收集二叉樹的無線傳感網數據收集方法，
[0010]利用隨機部署的無線傳感網節點，通過最近鄰居節點探尋、網絡區域建立、節點自定位、多重數據收集二叉樹建立，形成多個備選的數據收集路徑結構，並在此基礎上，利用基於節點數的時間片輪轉策略和面向網絡動態變化的數據收集樹重構，實現無線傳感網絡的數據收集。
[0011]進一步地，具體為:
[0012]步驟1:在矩形平面網絡中，部署η個無線傳感網節點，其中，含有存在若干個已知其自身位置信息的信標節點，基站位於網絡外圍邊緣處；
[0013]步驟2:網絡中的各節點，以廣播的方式，找尋距離自己最近的鄰居節點，並分布式地構建網絡區域；
[0014]步驟3:網絡中的所有非孤立的非信標節點自組織地完成自身位置信息的確定工作；
[0015]步驟4:從基站節點開始，建立第一棵備選數據收集二叉樹；
[0016]步驟5:從基站節點開始，建立第二棵備選數據收集二叉樹；
[0017]步驟6:根據步驟4和步驟5中的具體規則，從基站節點開始，繼續建立第三棵、第四棵……直至第k棵備選數據收集二叉樹，k的值可根據網絡規模和網絡數據傳輸量決定；
[0018]步驟7:基站節點根據其所建立的k棵備選數據收集二叉樹的結構情況，選擇一棵節點數最多的樹，作為「數據收集樹」;若符合條件的備選數據收集樹有多棵，則選擇樹中節點平均傳輸距離最短的一棵，作為「數據收集樹」;
[0019]步驟8:利用步驟7中被選中的「數據收集樹」，開始基於時間片輪轉的數據收集過程;
[0020]步驟9:當步驟7和步驟8中被選擇的數據收集樹中的節點因能耗過大而造成數據收集樹斷連時，將向基站進行通告，由基站從其它尚未被選中的備選數據收集樹中，按照步驟7的規則，選擇一棵，作為新的數據收集樹，並按照步驟8的規則，重新建立時間片輪轉的數據收集策略；同時，原數據收集樹作廢；
[0021]步驟10:在網絡運行了 Y個周期或當網絡中出現了新節點後，由基站節點發起重構「備選數據收集二叉樹樹」的命令，並轉步驟4，開始新一輪數據收集二叉樹的構建。
[0022]進一步地，步驟2中網絡區域的構建為:
[0023]步驟2-1:網絡中的各節點以其在收發狀態下的最小功率Pmin,分布式地廣播包含自身ID號的數據包；同時，開啟其內部計時器，定義計時器閾值為T ；
[0024]步驟2-2:在T時間內，若當前節點收到了一個及以上不同ID號的節點發來的數據包，則根據其到來時的信號強度大小，選擇信號強度最大的一個節點為其「最近鄰居點」，轉步驟2-3 ;若信號強度最大的鄰居節點不止一個，則當前節點選擇最先到達的數據包的ID號為其「最近鄰居點」，轉步驟2-3 ;若在T時間內，當前節點沒有收到任何數據包，則轉步驟 2-4 ；
[0025]步驟2-3:當前節點向其「最近鄰居點」發送一個確認包，並將該「最近鄰居節點」 ID號置入其緩存中，轉步驟2-6 ；
[0026]步驟2-4:若當前節點的發送功率P小於該節點所允許的最大發送功率Pmax,則當前節點增大其發送功率P後，重新廣播包含其自身ID號的數據包，同時，再次開啟其內部計時器，並設其閾值為T，轉步驟2-2 ;否則，轉步驟2-5 ；
[0027]步驟2-5:當前節點無法連通網絡中的其它任何節點，此時，將當前節點標記為孤立節點；孤立節點將不再參與網絡後續運行；
[0028]步驟2-6:收到確認包的節點將發來確認包的源節點的ID號置入其緩存中，同時，在網絡中的所有非孤立節點與其「最近鄰居節點」間，建立可達鏈路；此時，網絡將形成多個簇狀拓撲結構，將每個簇狀拓撲定義為一個區域。
[0029]進一步地,步驟3具體為:
[0030]步驟3-1:網絡中的所有非孤立的信標節點，以其最大發送功率Pmax廣播包含其ID號和其坐標信息的數據包；同時，網絡中的所有非孤立的非信標節點將其自身設置為接收狀態，以接收非孤立的信標節點的廣播包；
[0031]步驟3-2:若非孤立的非信標節點，收到3個或3個以上不同ID號的信標節點發送的廣播包，則利用極大似然估計法，估算自身的坐標值，並轉步驟3-3 ;否則轉步驟3-4 ;
[0032]步驟3-3:對於已經完成坐標值估算的非信標節點，若參與其坐標值估算的信標節點數大於5，或該非信標節點所估算出的坐標值與參與其坐標估算的所有信標節點所形成的多邊形的質心的坐標值誤差小於某一閾值時，則認為該非信標節點所估算出的坐標值可信，將該非信標節點標記為「可信節點」;同時，以其最大發送功率Pmax廣播包含其ID號和其坐標信息的數據包；
[0033]步驟3-4:若非孤立的非信標節點雖未能收到3個或3個以上不同ID號的信標節點發送的廣播包，但卻能夠收到3個或3個以上信標節點或「可信節點」的廣播包，則其仍可利用極大似然估計法，估算出自身的坐標值；否則，認為該節點無法完成對其自身坐標值的估算；
[0034]步驟3-5:將網絡中所有非孤立的信標節點和最終完成坐標值估計的非信標節點標記為「數據收集點」，以便其參與後續的多重數據融合樹的構建；最終無法完成坐標值估計的非孤立節點，將僅在後續步驟中參與數據傳輸，不參與多重數據融合樹的構建；
[0035]步驟3-6:網絡中所有的「數據收集點」將自身的坐標信息，以多跳傳遞的方式，反饋給基站。
[0036]進一步地，步驟4具體為:
[0037]步驟4-1:基站節點根據其所掌控的網絡內所有「數據收集點」的坐標情況，選擇平均距離與自身最近的一個區域，作為將要建立的備選數據收集二叉樹的第一層區域；
[0038]步驟4-2:基站節點在步驟4-1所選擇的區域中，選擇一個距離自身最近的「數據收集點」，作為基站的直接子節點，並將其標記為第一棵備選數據收集二叉樹的根節點，同時，基站節點同該節點建立點到點的連接；
[0039]步驟4-3:第一棵備選數據收集二叉樹的根節點進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離其自身最近的兩個區域；同時，根節點分別在這兩個區域中，各找尋一個距離其自身最近的「數據收集點」，並分別作為其左孩子和右孩子，建立到達它們的連接；
[0040]步驟4-4:左右兩個孩子節點分別進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離各自最近的兩個區域，且這些區域還需滿足以下條件，即任何一個區域中的數據收集點距離基站的平均距離，均大於等於當前節點所在區域中的所有數據收集點到達基站的平均距離；
[0041]步驟4-5:步驟4-4中的左右兩個孩子節點，分別選擇其所找尋到的區域中，距離自身最近的兩個數據收集點，作為自己的左右孩子節點，並建立到達它們的連接；
[0042]步驟4-6:步驟4-5中被選中的節點重複地按照步驟4-4和4-5的規則，選擇其自身的左右孩子節點，並建立到達它們的連接，直到沒有符合要求的區域或沒有符合要求的孩子節點為止；此時，第一棵備選數據收集二叉樹建立完成；步驟4-6終止時，網絡中的某些區域有可能未被選中，稱這樣的區域為「失聯區域」。
[0043]進一步地,步驟5具體為:
[0044]步驟5-1:基站節點在步驟4-1所選出的第一層區域中，選擇距離其自身次近的一個數據收集點，作為其所建立的第二棵備選數據收集二叉樹的根節點；同時，基站節點同該節點建立點到點的連接；
[0045]步驟5-2:第二棵備選數據收集二叉樹的根節點進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離其自身最近的兩個區域；同時，該根節點分別在這兩個區域中，各找尋一個距離其自身最近且尚未被其它備選數據收集二叉樹選中的「數據收集點」，分別作為其左孩子和右孩子，建立到達它們的連接；
[0046]步驟5-3:步驟5-2中的左右兩個孩子節點分別進行廣播探尋，按照步驟4_4中的方法各自選擇兩個區域；
[0047]步驟5-4:步驟5-2中的左右兩個孩子節點，分別選擇其所找尋到的區域中，距離自身最近且尚未被其它的備選數據收集二叉樹選中的兩個數據收集點，作為自己的左右孩子節點，並建立到達它們的連接；
[0048]步驟5-5:步驟5-4中被選中的節點重複地按照步驟5-3和5-4的規則，選擇其自身的左右孩子節點，並建立到達它們的連接，直到沒有符合要求的區域或沒有符合要求的孩子節點為止；此時，第二棵備選數據收集二叉樹建立完成；步驟5-5終止時，網絡中原本存在的「失聯區域」有可能被重新選中，此時，取消其「失聯區域」的標記。
[0049]進一步地,步驟8具體為:
[0050]步驟8-1:數據收集樹中各節點獲取其所在區域的節點數量信息Si,節點數量包含其自身在內，其中，i代表區域編號；
[0051]步驟8-2:數據收集樹中的各節點將其Si的值，通過多跳方式上報給基站，在上報過程中，各父節點需保存一份其所有直接子節點和間接子節點的Si值的副本；
[0052]步驟8-3:計算網絡中各區域在一個數據收集周期內所耗費的總時間。設定網絡中的各節點在一個數據收集周期內，耗費在其自身數據收集過程中的時間均為t，且忽略區域內節點之間的數據傳輸，並設定相鄰區域間數據傳輸的時間為τ ;則對於該數據收集樹中的任意一個葉節點所在的區域i，其在一個數據收集周期內，完成數據收集和傳輸的總時間為 Ti = SiXt+ τ ；
[0053]步驟8-4:根據步驟8-3所計算出的時間，設定網絡中各區域數據收集周期長度；對於數據收集樹中的任一葉節點a所在的區域i，根據步驟8-3，分配給該區域的時間片Ti=SiXt+ τ ;而對於數據收集樹中的任一中間節點b所在的區域j,分配給該區域的時間片長度L的大小，等於區域j自身進行數據收集和傳輸所需時間S^Xt+ τ，加上節點b的所有直接和間接孩子節點所屬區域進行數據收集及數據傳輸所耗費的時間總和；
[0054]令節點b的孩子節點所屬的各個區域中的節點個數分別為Q1, Q2,…Qq ；其中，q為b的孩子節點總數；則根據步驟8-3中的條件及二叉樹的性質可知，
T^S^t + r + ^xt + qxr其中，藝Q χ ?切x r是節點b的所有直接和間接孩子節點所
/=1..,

， 2=1
屬區域進行數據收集及數據傳輸所耗費的時間總和；








h
[0055]步驟8-5:根據步驟8-4，則網絡完成一次數據收集所需時間為Α = 其中h為


η ,
步驟7中所選中的數據收集樹中的節點總數；T即一個數據收集周期，而Ti則是在一個數據收集周期內，分配給各個區域的時間片長度；於是，網絡在一個數據收集周期內，按照上述時間片進行輪轉，最終在T時間內，完成一次數據收集。
[0056]本發明具備如下有益成果:
[0057]第一，構建多個備選的數據收集二叉樹，可較好地適應網絡的動態變化，增強數據收集的魯棒性；
[0058]第二，將網絡中最為接近的若干節點組織成一個區域，並在每個區域中選取一個節點作為數據收集二叉樹中的節點，有效節約了數據收集能耗；
[0059]第三，採用基於節點數的時間片輪轉方式進行數據收集，有效降低了數據收集過程中的衝突發生率，提升了數據收集效率；
[0060]第四，採用了周期性重構數據收集樹的策略，有效提升了網絡的適應性。

【專利附圖】

【附圖說明】
[0061]圖1是網絡初始部署的示意圖；
[0062]圖2是無線傳感網確保感知覆蓋的最大密度部署情況的說明示意圖；
[0063]圖3是無線傳感網確保感知覆蓋的最小密度部署情況的說明示意圖；
[0064]圖4是尋找最近鄰居節點並形成分區的說明示意圖；
[0065]圖5是符合定位條件的非信標節點完成定位的說明示意圖；
[0066]圖6是利用「升級」後的節點完成定位的說明示意圖；
[0067]圖7是建立第一棵備選數據收集二叉樹的說明示意圖；
[0068]圖8是建立第二棵備選數據收集二叉樹的說明示意圖；
[0069]圖9是建立第三棵備選數據收集二叉樹的說明示意圖；
[0070]圖10是被選中的數據收集樹及其時間片輪轉的說明示意圖；
[0071]圖11是第一棵數據收集樹失效後重新選擇數據收集樹的說明示意圖；
[0072]圖12是有節點失效或新節點加入後進行重構的備選數據收集樹的說明示意圖。

【具體實施方式】
[0073]下面結合附圖詳細說明本發明的優選實施例。
[0074]實施例提供了一種基於基於多重二叉樹的數據收集方法，分別通過最近鄰居節點探尋、網絡區域建立、節點自定位、多重數據收集二叉樹建立、基於時間片輪轉的數據收集和面向網絡動態變化的數據收集樹重構等過程，實現高效、穩定、節能的無線傳感網數據收集過程。其具體的
【發明內容】
主要包括如下六個階段。
[0075]第一階段:網絡部署階段。在該階段中，本發明在矩形網絡中，部署固定密度的無線傳感網節點。為了同時滿足網絡的感知覆蓋條件，本發明給出了最佳節點部署密度的計算方法；
[0076]第二節點:網絡區域劃分階段。在該階段中，網絡中的各節點以自組織方式，找尋距離自己最近的鄰居節點，並建立到達該鄰居節點的雙向連接。由於本發明僅需每個節點連接至距離其最近的鄰居節點，無形中降低了節點的通信能耗開銷。該階段結束後，網絡將被劃分為若干個獨立的區域；
[0077]第三階段:網絡中節點自定位階段。為了在建立多重數據收集二叉樹時找尋到任意兩個節點間的距離，需要首先對網絡中的節點進行定位。在本階段中，以信標節點廣播，非信標節點接收含坐標的廣播信息的方式進行測距，並利用極大似然估計法實現定位。而對於無法獲取到足夠信標節點信息的非信標節點，本階段採用定位結果精度較高的已定位節點「升級」的方式，對其進行定位；
[0078]第四階段:多棵備選的數據收集二叉樹的建立階段。在該階段，基站節點分別發起若干次「建樹」過程。每次「建樹」過程均在每個區域中找尋一個距離正在構建的數據收集二叉樹最近的節點，並將其加入到數據收集樹中，以確保所建立的數據收集樹中節點間的整體通信距離較短，從而節省數據收集和傳輸過程中的能耗；
[0079]第五階段:基於時間片輪轉的數據收集階段。在該階段，基站節點選擇一棵覆蓋面最廣的數據收集樹，並根據樹中各節點所在區域及其直接和間接子節點所在區域中的節點個數，制定針對各區域和數據收集樹中各節點的時間片。基站節點負責網絡整體時間片的輪轉。網絡中所有節點及其所在區域，以時間片輪轉的方式，開始周期性地數據收集過程；
[0080]第六階段:面向網絡動態變化的數據收集路徑重構節點。在該階段，本發明針對數據收集樹中的失效節點以及網絡中新加入的節點，提出了周期性地更新和重構多重數據收集二叉樹的過程，以提升本發明的魯棒性和適應性，進一步提升數據收集的效率。
[0081]實施例的具體步驟如下:
[0082]步驟1:在長寬分別為M和N的矩形平面網絡中，部署η個無線傳感網節點(以下簡稱為「節點」)。n = MXNX P ,且這η個節點中,存在若干個已知其自身位置信息的信標節點。基站位於網絡外圍邊緣處，如圖1所示，其中，標註了黑色圓心的節點為信標節點。P為網絡中所部署的節點密度。根據已有理論，在全向無線傳感器網絡中，為確保完全覆蓋，
2 2
需要部署的最大和最小節點密度分別為= 和P— = 3^βΓ2，分別如圖2和圖3所示，r為節點的感知半徑。故這裡定義P = (P max+P min)/2。
[0083]步驟2:網絡中的各節點，以廣播的方式，找尋距離自己最近的鄰居節點，並分布式地構建網絡區域。其具體步驟為:
[0084]步驟2-1:網絡中的各節點以其在收發狀態下的最小功率Pmin,分布式地廣播包含自身ID號的數據包。同時，開啟其內部計時器，定義計時器閾值為T ;
[0085]步驟2-2:在T時間內，若當前節點收到了一個及以上不同ID號的節點發來的數據包，則根據其到來時的信號強度大小，選擇信號強度最大的一個節點為其「最近鄰居點」，轉步驟2-3 ;若信號強度最大的鄰居節點不止一個，則當前節點選擇最先到達的數據包的ID號為其「最近鄰居點」，轉步驟2-3 ;若在T時間內，當前節點沒有收到任何數據包，則轉步驟 2-4 ；
[0086]步驟2-3:當前節點向其「最近鄰居點」發送一個確認包，並將該「最近鄰居節點」 ID號置入其緩存中，轉步驟2-6 ；
[0087]步驟2-4:若當前節點的發送功率P小於該節點所允許的最大發送功率Pmax,則當前節點增大其發送功率P後，重新廣播包含其自身ID號的數據包，同時，再次開啟其內部計時器，並設其閾值為T，轉步驟2-2 ;否則，轉步驟2-5 ；
[0088]步驟2-5:當前節點無法連通網絡中的其它任何節點，此時，將當前節點標記為孤立節點，如圖4中的節點A。孤立節點將不再參與網絡後續運行；
[0089]步驟2-6:收到確認包的節點將發來確認包的源節點的ID號置入其緩存中，同時，在網絡中的所有非孤立節點與其「最近鄰居節點」間，建立可達鏈路。此時，網絡將形成多個簇狀拓撲結構，如圖4所示。將每個簇狀拓撲定義為一個區域。
[0090]步驟3:網絡中的所有非孤立的非信標節點自組織地完成自身位置信息的確定工作。其具體步驟為:
[0091]步驟3-1:網絡中的所有非孤立的信標節點，以其最大發送功率Pmax廣播包含其ID號和其坐標信息的數據包。同時，網絡中的所有非孤立的非信標節點將其自身設置為接收狀態，以接收非孤立的信標節點的廣播包；
[0092]步驟3-2:若非孤立的非信標節點，收到3個或3個以上不同ID號的信標節點發送的廣播包，則利用極大似然估計法，估算自身的坐標值，並轉步驟3-3，如圖5中的節點B，圖5中的虛線箭頭代表信標節點的廣播包到達節點B ;否則轉步驟3-4 ；
[0093]步驟3-3:對於已經完成坐標值估算的非信標節點，若參與其坐標值估算的信標節點數大於5，或該非信標節點所估算出的坐標值與參與其坐標估算的所有信標節點所形成的多邊形的質心的坐標值誤差小於某一閾值時，則認為該非信標節點所估算出的坐標值可信，將該非信標節點標記為「可信節點」。同時，以其最大發送功率Pmax廣播包含其ID號和其坐標信息的數據包。此步驟的目的在於，將精度較高的已定位節點，臨時「升級」為信標節點，以便讓更多的節點完成定位，如圖6中的節點B，假設B點符合「升級」的條件，則此時B的廣播包可到達圖6中的C、D、E、F等非信標節點；
[0094]步驟3-4:若非孤立的非信標節點雖未能收到3個或3個以上不同ID號的信標節點發送的廣播包，但卻能夠收到3個或3個以上信標節點或「可信節點」的廣播包，則其仍可利用極大似然估計法，估算出自身的坐標值。如圖6中的節點C，儘管其僅能夠收到G、H等兩個信標節點的廣播包，但卻還可以收到已定位的節點B的廣播包，滿足定位條件，可以完成定位；否則，認為該節點無法完成對其自身坐標值的估算；
[0095]步驟3-5:將網絡中所有非孤立的信標節點和最終完成坐標值估計的非信標節點標記為「數據收集點」，以便其參與後續的多重數據融合樹的構建；最終無法完成坐標值估計的非孤立節點，將僅在後續步驟中參與數據傳輸，不參與多重數據融合樹的構建；
[0096]步驟3-6:網絡中所有的「數據收集點」將自身的坐標信息，以多跳傳遞的方式，反饋給基站。
[0097]步驟4:從基站節點開始，建立第一棵備選數據收集二叉樹。其具體步驟為:
[0098]步驟4-1:基站節點根據其所掌控的網絡內所有「數據收集點」的坐標情況，選擇平均距離與自身最近的一個區域，作為將要建立的備選數據收集二叉樹的第一層區域，如圖7中的區域I。
[0099]步驟4-2:基站節點在步驟4-1所選擇的區域中，選擇一個距離自身最近的「數據收集點」，作為基站的直接子節點，並將其標記為第一棵備選數據收集二叉樹的根節點，同時，基站節點同該節點建立點到點的連接，如圖7中的節點I,為顯著標示,標註其為灰色。
[0100]步驟4-3:第一棵備選數據收集二叉樹的根節點進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離其自身最近的兩個區域，如圖7中的區域2和區域3。同時，根節點分別在這兩個區域中，各找尋一個距離其自身最近的「數據收集點」，並分別作為其左孩子和右孩子，如圖7中的節點J和節點B，建立到達它們的連接，在圖7中，以黑色粗實線表示；
[0101]步驟4-4:左右兩個孩子節點分別進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離各自最近的兩個區域，且這些區域還需滿足以下條件，即任何一個區域中的數據收集點距離基站的平均距離，均大於等於當前節點所在區域中的所有數據收集點到達基站的平均距離。如圖7所示，區域4和區域5為距離節點J最近的兩個區域，且區域4和區域5中的數據收集點距離基站的平均距離大於節點J所在的區域2中的所有數據收集點到達基站的平均距離，而區域6和區域7則是符合上述條件的距離節點B最近的兩個區域；
[0102]步驟4-5:步驟4-4中的左右兩個孩子節點，分別選擇其所找尋到的區域中，距離自身最近的兩個數據收集點，作為自己的左右孩子節點(如圖7中的節點K、L、H和M點。為顯著標示，標註其為灰色)，並建立到達它們的連接，以黑色粗實線表示；
[0103]步驟4-6:步驟4-5中被選中的節點重複地按照步驟4-4和4_5的規則，選擇其自身的左右孩子節點，並建立到達它們的連接，直到沒有符合要求的區域或沒有符合要求的孩子節點為止。此時，第一棵備選數據收集二叉樹建立完成，如圖7所示。步驟4-6終止時，網絡中的某些區域有可能未被選中，稱這樣的區域為「失聯區域」，如圖7中的區域8，為顯著標示，將該區域底色標註為灰色。
[0104]步驟5:從基站節點開始，建立第二棵備選數據收集二叉樹。其具體步驟為:
[0105]步驟5-1:基站節點在步驟4-1所選出的第一層區域中，選擇距離其自身次近的一個數據收集點，作為其所建立的第二棵備選數據收集二叉樹的根節點，如圖8中的節點N，為顯著標示，將該節點標註為豎線陰影；同時，基站節點同該節點建立點到點的連接，在圖8中，以點粗虛線表示；
[0106]步驟5-2:第二棵備選數據收集二叉樹的根節點進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離其自身最近的兩個區域，如圖8中的區域2和區域4。同時，該根節點分別在這兩個區域中，各找尋一個距離其自身最近且尚未被其它備選數據收集二叉樹選中的「數據收集點」，分別作為其左孩子和右孩子(如圖8中的節點O和節點P。為顯著，同樣標註其為豎線陰影)，建立到達它們的連接；
[0107]步驟5-3:步驟5-2中的左右兩個孩子節點分別進行廣播探尋，按照步驟4-4中的方法各自選擇兩個區域。如圖8所示，區域5和區域3為距離節點P最近的且符合步驟4-4要求的兩個區域，而對於節點0，則找不到符合條件的區域；
[0108]步驟5-4:步驟5-2中的左右兩個孩子節點，分別選擇其所找尋到的區域中，距離自身最近且尚未被其它的備選數據收集二叉樹選中的兩個數據收集點，作為自己的左右孩子節點(如圖8中的節點Q和C。為顯著，同樣標註其為豎線陰影)，並建立到達它們的連接；
[0109]步驟5-5:步驟5-4中被選中的節點重複地按照步驟5-3和5_4的規則，選擇其自身的左右孩子節點，並建立到達它們的連接，直到沒有符合要求的區域或沒有符合要求的孩子節點為止。此時，第二棵備選數據收集二叉樹建立完成，如圖8所示。步驟5-5終止時，網絡中原本存在的「失聯區域」有可能被重新選中，此時，取消其「失聯區域」的標記，如圖8中的區域8所示。
[0110]步驟6:根據步驟4和步驟5中的具體規則，從基站節點開始，繼續建立第三棵、第四棵……直至第k棵備選數據收集二叉樹，k的值可根據網絡規模和網絡數據傳輸量決定。圖9為一個建立了 3棵備選數據收集二叉樹的無線傳感網，第三棵備選數據收集二叉樹中的節點標記為黑色，之間用黑色粗虛線連接。
[0111]步驟7:基站節點根據其所建立的k棵備選數據收集二叉樹的結構情況，選擇一棵節點數最多的樹，作為「數據收集樹」，以確保該備選數據收集二叉樹能夠收集網絡中儘可能多的區域產生的數據。例如，圖7至圖9分別展示了網絡中的三棵備選數據收集二叉樹的建立過程，而圖8中所建立的第二棵樹具有最多的節點，故選擇其作為「數據收集樹」;若符合條件的備選數據收集樹有多棵，則選擇樹中節點平均傳輸距離最短的一棵，作為「數據收集樹」。
[0112]步驟8:利用步驟7中被選中的「數據收集樹」，開始基於時間片輪轉的數據收集過程。其具體步驟為:
[0113]步驟8-1:數據收集樹中各節點獲取其所在區域的節點數量信息Si (節點數量包含其自身在內)，其中，i代表區域編號；
[0114]步驟8-2:數據收集樹中的各節點將其Si的值，通過多跳方式上報給基站。在上報過程中，各父節點需保存一份其所有直接子節點和間接子節點的Si值的副本；
[0115]步驟8-3:計算網絡中各區域在一個數據收集周期內所耗費的總時間。設定網絡中的各節點在一個數據收集周期內，耗費在其自身數據收集過程中的時間均為t，且忽略區域內節點之間的數據傳輸，並設定相鄰區域間數據傳輸的時間為τ。則對於該數據收集樹中的任意一個葉節點所在的區域i，其在一個數據收集周期內，完成數據收集和傳輸的總時間為Ti = SiXt+τ。如圖10所示的數據收集樹中，葉節點所在的區域4、6、7、8在一個數據收集周期內的所耗費的總時間將分別為:T4 = 5t+ τ、Τ6 = 4t+ τ、T7 = 3t+ τ和Τ8 =
2t+ τ ；
[0116]步驟8-4:根據步驟8-3所計算出的時間，設定網絡中各區域數據收集周期長度。對於數據收集樹中的任一葉節點a所在的區域i，根據步驟8-3，分配給該區域的時間片Ti=SiXt+ τ。而對於數據收集樹中的任一中間節點b所在的區域j,分配給該區域的時間片長度Tj的大小，等於區域j自身進行數據收集和傳輸所需時間SjXt+ τ，加上節點b的所有直接和間接孩子節點所屬區域進行數據收集及數據傳輸所耗費的時間總和。令節點b的孩子節點所屬的各個區域中的節點個數分別為Ql，Q2,-Qq0其中，q為b的孩子節點總數。則根據步驟8-3中的條件及二叉樹的性質可知，++ 其中，
料O是節點b的所有直接和間接孩子節點所屬區域進行數據收集及數據傳輸所
1=\
耗費的時間總和。








h
[0117]步驟8-5:根據步驟8-4，則網絡完成一次數據收集所需時間為Τ = 其中h為步驟7中所選中的數據收集樹中的節點總數。T即一個數據收集周期，而Ti則是在一個數據收集周期內，分配給各個區域的時間片長度。於是，網絡在一個數據收集周期內，按照上述時間片進行輪轉，最終在T時間內，完成一次數據收集。
[0118]步驟9:當步驟7和步驟8中被選擇的數據收集樹中的節點因能耗過大而造成數據收集樹斷連時，將向基站進行通告，由基站從其它尚未被選中的備選數據收集樹中，按照步驟7的規則，選擇一棵，作為新的數據收集樹，並按照步驟8的規則，重新建立時間片輪轉的數據收集策略。同時，原數據收集樹作廢。如，假設圖10中的數據收集樹在運轉了一段時間後，因節點P能耗過大而斷連，此時，基站重新選擇數據收集樹，如圖11所示，同時，圖10中的數據收集樹作廢。
[0119]步驟10:由於無線傳感網為動態網絡，除了節點失效的情況外，需考慮新節點加入的情況。故在網絡運行了 Y個周期或當網絡中出現了新節點後，由基站節點發起重構「備選數據收集二叉樹樹」的命令，並轉步驟4，開始新一輪數據收集二叉樹的構建。如圖12所示，當網絡中出現了新節點Y且節點L失效後，基站節點重新構建了 3棵「備選數據收集二叉樹」。
【權利要求】
1.一種基於多重數據收集二叉樹的無線傳感網數據收集方法，其特徵在於: 利用隨機部署的無線傳感網節點，通過最近鄰居節點探尋、網絡區域建立、節點自定位、多重數據收集二叉樹建立，形成多個備選的數據收集路徑結構，並在此基礎上，利用基於節點數的時間片輪轉策略和面向網絡動態變化的數據收集樹重構，實現無線傳感網絡的數據收集。
2.如權利要求1所述的基於多重數據收集二叉樹的無線傳感網數據收集方法，其特徵在於，具體為: 步驟1:在矩形平面網絡中，部署η個無線傳感網節點，其中，含有存在若干個已知其自身位置信息的信標節點，基站位於網絡外圍邊緣處； 步驟2:網絡中的各節點，以廣播的方式，找尋距離自己最近的鄰居節點，並分布式地構建網絡區域； 步驟3:網絡中的所有非孤立的非信標節點自組織地完成自身位置信息的確定工作； 步驟4:從基站節點開始，建立第一棵備選數據收集二叉樹； 步驟5:從基站節點開始，建立第二棵備選數據收集二叉樹；步驟6:根據步驟4和步驟5中的具體規則，從基站節點開始，繼續建立第三棵、第四棵……直至第k棵備選數據收集二叉樹，k的值可根據網絡規模和網絡數據傳輸量決定；步驟7:基站節點根據其所建立的k棵備選數據收集二叉樹的結構情況，選擇一棵節點數最多的樹，作為「數據收集樹」;若符合條件的備選數據收集樹有多棵，則選擇樹中節點平均傳輸距離最短的一棵，作為「數據收集樹」;步驟8:利用步驟7中被選中的「數據收集樹」，開始基於時間片輪轉的數據收集過程；步驟9:當步驟7和步驟8中被選擇的數據收集樹中的節點因能耗過大而造成數據收集樹斷連時，將向基站進行通告，由基站從其它尚未被選中的備選數據收集樹中，按照步驟7的規則，選擇一棵，作為新的數據收集樹，並按照步驟8的規則，重新建立時間片輪轉的數據收集策略；同時，原數據收集樹作廢； 步驟10:在網絡運行了 Y個周期或當網絡中出現了新節點後，由基站節點發起重構「備選數據收集二叉樹樹」的命令，並轉步驟4，開始新一輪數據收集二叉樹的構建。
3.如權利要求2所述的基於多重數據收集二叉樹的無線傳感網數據收集方法，其特徵在於，步驟2中網絡區域的構建為: 步驟2-1:網絡中的各節點以其在收發狀態下的最小功率Pmin,分布式地廣播包含自身ID號的數據包；同時，開啟其內部計時器，定義計時器閾值為T ； 步驟2-2:在T時間內，若當前節點收到了一個及以上不同ID號的節點發來的數據包，則根據其到來時的信號強度大小，選擇信號強度最大的一個節點為其「最近鄰居點」，轉步驟2-3 ;若信號強度最大的鄰居節點不止一個，則當前節點選擇最先到達的數據包的ID號為其「最近鄰居點」，轉步驟2-3 ;若在T時間內，當前節點沒有收到任何數據包，則轉步驟2-4 ； 步驟2-3:當前節點向其「最近鄰居點」發送一個確認包，並將該「最近鄰居節點」 ID號置入其緩存中，轉步驟2-6; 步驟2-4:若當前節點的發送功率P小於該節點所允許的最大發送功率Pmax,則當前節點增大其發送功率P後，重新廣播包含其自身ID號的數據包，同時,再次開啟其內部計時器，並設其閾值為T，轉步驟2-2 ;否則，轉步驟2-5 ； 步驟2-5:當前節點無法連通網絡中的其它任何節點，此時，將當前節點標記為孤立節點；孤立節點將不再參與網絡後續運行； 步驟2-6:收到確認包的節點將發來確認包的源節點的ID號置入其緩存中，同時，在網絡中的所有非孤立節點與其「最近鄰居節點」間，建立可達鏈路；此時，網絡將形成多個簇狀拓撲結構，將每個簇狀拓撲定義為一個區域。
4.如權利要求3所述的基於多重數據收集二叉樹的無線傳感網數據收集方法，其特徵在於，步驟3具體為: 步驟3-1:網絡中的所有非孤立的信標節點，以其最大發送功率Pmax廣播包含其ID號和其坐標信息的數據包；同時，網絡中的所有非孤立的非信標節點將其自身設置為接收狀態，以接收非孤立的信標節點的廣播包； 步驟3-2:若非孤立的非信標節點，收到3個或3個以上不同ID號的信標節點發送的廣播包，則利用極大似然估計法，估算自身的坐標值，並轉步驟3-3 ;否則轉步驟3-4 ； 步驟3-3:對於已經完成坐標值估算的非信標節點，若參與其坐標值估算的信標節點數大於5，或該非信標節點所估算出的坐標值與參與其坐標估算的所有信標節點所形成的多邊形的質心的坐標值誤差小於某一閾值時，則認為該非信標節點所估算出的坐標值可信，將該非信標節點標記為「可信節點」;同時，以其最大發送功率Pmax廣播包含其ID號和其坐標信息的數據包； 步驟3-4:若非孤立的非信標節點雖未能收到3個或3個以上不同ID號的信標節點發送的廣播包，但卻能夠收到3個或3個以上信標節點或「可信節點」的廣播包，則其仍可利用極大似然估計法，估算出自身的坐標值；否則，認為該節點無法完成對其自身坐標值的估算； 步驟3-5:將網絡中所有非孤立的信標節點和最終完成坐標值估計的非信標節點標記為「數據收集點」，以便其參與後續的多重數據融合樹的構建；最終無法完成坐標值估計的非孤立節點，將僅在後續步驟中參與數據傳輸，不參與多重數據融合樹的構建； 步驟3-6:網絡中所有的「數據收集點」將自身的坐標信息，以多跳傳遞的方式，反饋給基站O
5.如權利要求4所述的基於多重數據收集二叉樹的無線傳感網數據收集方法，其特徵在於，步驟4具體為: 步驟4-1:基站節點根據其所掌控的網絡內所有「數據收集點」的坐標情況，選擇平均距離與自身最近的一個區域，作為將要建立的備選數據收集二叉樹的第一層區域； 步驟4-2:基站節點在步驟4-1所選擇的區域中，選擇一個距離自身最近的「數據收集點」，作為基站的直接子節點，並將其標記為第一棵備選數據收集二叉樹的根節點，同時，基站節點同該節點建立點到點的連接； 步驟4-3:第一棵備選數據收集二叉樹的根節點進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離其自身最近的兩個區域；同時，根節點分別在這兩個區域中，各找尋一個距離其自身最近的「數據收集點」，並分別作為其左孩子和右孩子，建立到達它們的連接; 步驟4-4:左右兩個孩子節點分別進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離各自最近的兩個區域，且這些區域還需滿足以下條件，即任何一個區域中的數據收集點距離基站的平均距離，均大於等於當前節點所在區域中的所有數據收集點到達基站的平均距離； 步驟4-5:步驟4-4中的左右兩個孩子節點，分別選擇其所找尋到的區域中，距離自身最近的兩個數據收集點，作為自己的左右孩子節點，並建立到達它們的連接； 步驟4-6:步驟4-5中被選中的節點重複地按照步驟4-4和4-5的規則，選擇其自身的左右孩子節點，並建立到達它們的連接，直到沒有符合要求的區域或沒有符合要求的孩子節點為止；此時，第一棵備選數據收集二叉樹建立完成；步驟4-6終止時，網絡中的某些區域有可能未被選中，稱這樣的區域為「失聯區域」。
6.如權利要求5所述的基於多重數據收集二叉樹的無線傳感網數據收集方法，其特徵在於，步驟5具體為: 步驟5-1:基站節點在步驟4-1所選出的第一層區域中，選擇距離其自身次近的一個數據收集點，作為其所建立的第二棵備選數據收集二叉樹的根節點；同時，基站節點同該節點建立點到點的連接； 步驟5-2:第二棵備選數據收集二叉樹的根節點進行廣播探尋，利用各節點的自身坐標，計算並找尋出距離其自身最近的兩個區域；同時，該根節點分別在這兩個區域中，各找尋一個距離其自身最近且尚未被其它備選數據收集二叉樹選中的「數據收集點」，分別作為其左孩子和右孩子，建立到達它們的連接； 步驟5-3:步驟5-2中的左右兩個孩子節點分別進行廣播探尋，按照步驟4-4中的方法各自選擇兩個區域； 步驟5-4:步驟5-2中的左右兩個孩子節點，分別選擇其所找尋到的區域中，距離自身最近且尚未被其它的備選數據收集二叉樹選中的兩個數據收集點，作為自己的左右孩子節點，並建立到達它們的連接； 步驟5-5:步驟5-4中被選中的節點重複地按照步驟5-3和5-4的規則，選擇其自身的左右孩子節點，並建立到達它們的連接，直到沒有符合要求的區域或沒有符合要求的孩子節點為止；此時，第二棵備選數據收集二叉樹建立完成；步驟5-5終止時，網絡中原本存在的「失聯區域」有可能被重新選中，此時，取消其「失聯區域」的標記。
7.如權利要求1-6任一項所述的基於多重數據收集二叉樹的無線傳感網數據收集方法，其特徵在於，步驟8具體為: 步驟8-1:數據收集樹中各節點獲取其所在區域的節點數量信息Si,節點數量包含其自身在內，其中，i代表區域編號； 步驟8-2:數據收集樹中的各節點將其Si的值，通過多跳方式上報給基站，在上報過程中，各父節點需保存一份其所有直接子節點和間接子節點的Si值的副本； 步驟8-3:計算網絡中各區域在一個數據收集周期內所耗費的總時間；設定網絡中的各節點在一個數據收集周期內，耗費在其自身數據收集過程中的時間均為t，且忽略區域內節點之間的數據傳輸，並設定相鄰區域間數據傳輸的時間為τ ;則對於該數據收集樹中的任意一個葉節點所在的區域i，其在一個數據收集周期內，完成數據收集和傳輸的總時間為Ti = Si X t+ τ ； 步驟8-4:根據步驟8-3所計算出的時間，設定網絡中各區域數據收集周期長度；對於數據收集樹中的任一葉節點a所在的區域i,根據步驟8-3,分配給該區域的時間片Ti =SiXt+ τ ;而對於數據收集樹中的任一中間節點b所在的區域j，分配給該區域的時間片長度L的大小，等於區域j自身進行數據收集和傳輸所需時間S^Xt+ τ，加上節點b的所有直接和間接孩子節點所屬區域進行數據收集及數據傳輸所耗費的時間總和；令節點b的孩子節點所屬的各個區域中的節點個數分別為Q1, Q2,…Qq ；其中，q為b的孩子節點總數；則根據步驟8-3中的條件及二叉樹的性質可知，T^SjXt + T + ^xt + qxr其中，藝β, X ?切X r是節點b的所有直接和間接孩子節點所
-1 ； (=1屬區域進行數據收集及數據傳輸所耗費的時間總和；







h步驟8-5:根據步驟8-4，則網絡完成一次數據收集所需時間為F = 其中h為步驟


問 ，7中所選中的數據收集樹中的節點總數；T即一個數據收集周期，而Ti則是在一個數據收集周期內，分配給各個區域的時間片長度；網絡在一個數據收集周期內，按照上述時間片進行輪轉，最終在T時間內，完成一次數據收集。
【文檔編號】H04W16/18GK104185191SQ201410423902
【公開日】2014年12月3日 申請日期:2014年8月26日 優先權日:2014年8月26日
【發明者】沙超, 沈天呈, 宋燕琪, 李靜, 邱建美, 陳歡, 王汝傳, 黃海平 申請人:南京郵電大學