無線傳感器數據收集時隙分配算法范文

本站小編為你精心準備了無線傳感器數據收集時隙分配算法參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

摘要:對數據收集時延進行研究，先將最小收集時延問題進行形式化表述，并建立目標函數;依據節點剩余能量，并結合克魯斯卡爾(Kruskal)算法構成最小生成樹;依據最小生成樹分配數據收集時隙。實驗數據表明:提出的時隙分配算法能夠有效地降低收集時延，并降低了能耗。

關鍵詞:無線傳感器網絡;數據收集;最小生成樹;能耗;分配時隙

引言

收集數據是無線傳感器網絡(wirelesssensornetworks，WSNs)最基礎的任務［1，2］。針對數據收集的WSNs，常將網絡內所有傳感節點構建為以基站為根的樹結構(treestruc-ture)［3，4］，也稱為基于樹的數據收集問題。根據節點融合數據，該問題可分為非融合數據收集和融合數據收集。在非融合數據收集中，基站直接接收所有節點發送的數據，并不采集任何融合措施。數據收集樹(datacollectiontree，DCT)的中間節點比其后裔節點(descendants)需要更多傳輸時隙。原因在于，中間節點不僅要傳輸自己的數據，還要給其后裔節點轉發數據。而在融合數據收集方案中，傳感節點將其來自后裔節點的數據與自己的數據進行融合，再將這些融合數據傳輸至其父節點［5，6］。本文以WSNs內的非融合數據收集問題為研究內容。針對非融合數據收集問題，現存的分配算法主要關注于依據樹結構，如何快速地將傳感節點數據傳輸至基站，即以少的時隙數完成數據收集。如ZhaoW［7］提出基于Colouring的分配算法，已用的Colour數據等于用于數據收集的時隙數。文獻［7］分析多個算法，如時隙分配、信道分配以及樹構建。類似地，文獻［8，9］研究數據收集的最低時延。為此，本文提出有效數據收集時隙分配算法。實驗數據表明，提出的時隙分配算法能夠有效地降低數據收集時延，并降低了能耗。

1約束條件及問題描述

1．1約束條件

用圖G=(V，E)表述傳感網絡，其中，V為頂點集，E為邊。若兩節點在彼此的通信范圍內，則這兩個節點的通信鏈路就存在。假定網絡內只有一個基站，并由此基站在每個抽樣間隔內收集傳感節點的數據。類似于文獻［3，4］，網絡內節點以數據收集樹DCT進行管理，即Tree=(VT，ET)，并以基站為根。其中，VT=V，ETE。在每個抽樣間隔內，假定傳感節點以概率p產生一個傳感節點數據包，然后再以多跳方式將數據包傳輸至基站。將時間劃分為m個時隙，即t={TS1，TS2，…，TSm}。其中TSm表示最后一個時隙，在這個時隙內，基站可能從其后裔節點接收數據包。顯然，m是要求收集所有數據的總的時隙數，其反映了數據收集過程的時延。此外，每個節點有足夠大的緩存區，在轉發數據前，能夠緩存所接收的數據包。

1．2問題描述

本文對要解決的問題進行形式化表述。對于給定的樹T，每個節點v要求多個發送時隙，用于傳輸自身的數據和轉發其后裔節點數據。為了能夠成功接收數據，所分配給節點的時隙要滿足兩個條件:1)所分配的時隙能夠完成數據的傳輸;2)所分配的傳輸時隙無碰撞。具體而言，假定節點v所分配的時隙表示為ST(v)，ST(v)需滿足的兩個條件為式中Ch(v)為節點v的孩子節點。式(1)規定ST(v)內時隙個數應大于其所有孩子節點所分配的時隙數之和。而式(2)規定，給節點v所分配的時隙就與其二跳鄰居節點所分配的時隙沒有交集，即無碰撞，其中，Cs(v)表示節點v的二跳鄰居節點所分配的時隙數。本文要解決的問題就是給DCT內每個節點分配時隙，并減少數據收集時隙。假定，在每個抽樣間隔內，每個節點均有感測數據要傳輸，為此，需要給每個節點分配時隙。而對于每個葉節點，只需要分配一個時隙用于傳輸自身數據。所謂葉節點就是指其無孩子節點，即

2時隙分配

用ti(v)表示節點v時隙集ST(v)內第i個時隙，且ST(v)內時隙以升序排列，ti(v)∈ST(v)，1≤i≤|ST(v)|。由于每個節點均有數據包會傳輸，需要給網絡內每個節點分配時隙。因此，以迭代方式工作，直到每個節點被分配了足夠傳輸時延，即滿足式(1)。在每次迭代，時隙分配以準備就序節點(readynode，RN)開始。所謂RN就是指它的后裔節點已全部分配了時隙。

2．1兩類時隙

節點除了傳輸自己的數據外，還需轉發孩子節點的數據。這兩類數據均需要分配時隙。因此，可將時隙分為兩類:1)用于節點傳輸自身數據的時隙，稱為傳輸時隙。因此，在每個間隔，只需給節點分配一個時隙。據此，可在無碰撞條件下，盡可能早地給節點分配傳輸時隙。假定在第k次迭代，節點v的傳輸時隙stk(v)滿足式(8)可知，分配給節點v的時隙不能與其二跳鄰居節點所分配的時隙重復(t(Uy∈Cs(v)ST(y)))。并且是在ST(v)內選擇一個最靠前的時隙作為傳輸時隙。2)轉發時隙，用于轉發來自后裔節點的數據。由于節點需要負責轉發它的所有后裔節點數據，給節點分配的轉發時隙就等于其后裔節點數。在每次迭代中，只給一個節點分配一個時隙，節點v所分配的時隙要在它的所有孩子節點分配完時隙后。假定它的所有孩子節點在k次迭代之前已分配了時隙，那節點v應在i＞k次迭代分配轉發時隙。因此，給節點v分配的轉發時隙為式中t＞max{stk(x)，x∈Ch(v)}為所分配的時隙要在其孩子節點時隙后。先從子樹開始分配時隙，先給葉節點分配，然后是此葉節點的父節點。以圖1為例，假定節點u有3三個孩子節點{θ1，θ2，θ3)，且每孩子節點以自己構建子樹，且分別表示為T(θ1)，T(θ2)，T(θ3)。

2．2基于節點剩余能量的最小生成樹

本文利用節點剩余能量作為邊權重，再利用克魯斯卡爾(Kruskal)算法［10］構建最小生成樹。Kruskal算法是構建最小生成樹的常用算法，是通過邊權重產生最小連通圖。其思路簡述如下:先從E中選擇權重最小的邊，若該邊的頂點在Γ中不同的連通分量上，則該邊加入Γ中，否則丟棄。然后，再從E中選擇權重最小的邊，依次類推，直到所有頂點均連通在同一個拓撲圖內。以圖2為例，描述構建最小生成樹的原理。圖中標的數字表述節點剩余能量。如節點2的剩余能量為30。依據節點剩余能量計算邊權重，每條邊權重等于邊的兩端節點剩余能量之和。如由節點5和節點2構成的邊，其邊權重為20與30的和，即50。先從找到最大權重的邊，即從它的一跳鄰居節點選擇剩余能量最大的節點作為父節點，然后構成一個最小生成樹。此外，基站的剩余能量無限大，因此，節點1，2，3都將基站作為父節點。實際上，其為樹的根節點。

2．3分配時隙的流程

先利用Kruskal算法構成生成樹，然后給樹中的每個節點分配時隙，分配過程的偽代碼如下

3性能仿真

3．1仿真參數

引用NS3［11］網絡仿真器建立仿真平臺?？紤]100個隨機在分布于100m×100m區域。每個節點的通信半徑為15m。100個節點內只有部分節點在每輪產生數據包，即產生數據包的概率p從0～1變化。同時，為了更好地分析本文所提出的時隙分配算法性能，選擇TPO［7］作為參照，每次實驗獨立重復200次，并取平均值作為最終的仿真數據。

3．2數據分析

首先分析數據收集時延，實驗數據如圖3所示。其中，數據收集時延是指總共需要的時隙數。可知，提出的時隙分配算法的數據收集時延低于其他各算法。與TPO算法相比，提出的時隙分配算法的時延數平均降低了32．4%。原因在于，時隙分配算法能夠依據Kruskal算法構建最小生成樹，再依據此樹分配時隙，減少了所分配的時隙數。接下來，分析節點能耗。引用文獻［12］的Bluetooth4．1標準的能量模型，并假定每個節點中的初始能量為3J。能耗數據如圖4所示?？芍?，提出時隙分配算法有效地降低了總體能量，原因在于分配算法利用節點剩余能量構建最小生成樹，再依據最小生成樹合理分配時隙，進而降低了能耗。與TPO算法相比，提出的時隙分配算法的能耗平均降低了約5．4%。

4結論

本文針對無線傳感網絡的數據收集時延問題，展開研究，并提出新的時隙分配算法，進而降低數據收集時延，同時減少節點能耗。利用克魯斯卡爾算法建立最小生成樹，再依據最小生成樹分配時隙。實驗數據表明，提出的分配算法能夠合理地給節點分配時隙，并減少了節點能耗。

作者：白秋產 王亮明 單位：淮陰工學院