本站小編為你精心準(zhǔn)備了無(wú)線傳感器數(shù)據(jù)收集時(shí)隙分配算法參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要:對(duì)數(shù)據(jù)收集時(shí)延進(jìn)行研究，先將最小收集時(shí)延問(wèn)題進(jìn)行形式化表述，并建立目標(biāo)函數(shù);依據(jù)節(jié)點(diǎn)剩余能量，并結(jié)合克魯斯卡爾(Kruskal)算法構(gòu)成最小生成樹(shù);依據(jù)最小生成樹(shù)分配數(shù)據(jù)收集時(shí)隙。實(shí)驗(yàn)數(shù)據(jù)表明:提出的時(shí)隙分配算法能夠有效地降低收集時(shí)延，并降低了能耗。

關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò);數(shù)據(jù)收集;最小生成樹(shù);能耗;分配時(shí)隙

引言

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

1約束條件及問(wèn)題描述

1．1約束條件

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

1．2問(wèn)題描述

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

2時(shí)隙分配

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

2．1兩類時(shí)隙

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

2．2基于節(jié)點(diǎn)剩余能量的最小生成樹(shù)

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

2．3分配時(shí)隙的流程

先利用Kruskal算法構(gòu)成生成樹(shù)，然后給樹(shù)中的每個(gè)節(jié)點(diǎn)分配時(shí)隙，分配過(guò)程的偽代碼如下

3性能仿真

3．1仿真參數(shù)

引用NS3［11］網(wǎng)絡(luò)仿真器建立仿真平臺(tái)。考慮100個(gè)隨機(jī)在分布于100m×100m區(qū)域。每個(gè)節(jié)點(diǎn)的通信半徑為15m。100個(gè)節(jié)點(diǎn)內(nèi)只有部分節(jié)點(diǎn)在每輪產(chǎn)生數(shù)據(jù)包，即產(chǎn)生數(shù)據(jù)包的概率p從0～1變化。同時(shí)，為了更好地分析本文所提出的時(shí)隙分配算法性能，選擇TPO［7］作為參照，每次實(shí)驗(yàn)獨(dú)立重復(fù)200次，并取平均值作為最終的仿真數(shù)據(jù)。

3．2數(shù)據(jù)分析

首先分析數(shù)據(jù)收集時(shí)延，實(shí)驗(yàn)數(shù)據(jù)如圖3所示。其中，數(shù)據(jù)收集時(shí)延是指總共需要的時(shí)隙數(shù)。可知，提出的時(shí)隙分配算法的數(shù)據(jù)收集時(shí)延低于其他各算法。與TPO算法相比，提出的時(shí)隙分配算法的時(shí)延數(shù)平均降低了32．4%。原因在于，時(shí)隙分配算法能夠依據(jù)Kruskal算法構(gòu)建最小生成樹(shù)，再依據(jù)此樹(shù)分配時(shí)隙，減少了所分配的時(shí)隙數(shù)。接下來(lái)，分析節(jié)點(diǎn)能耗。引用文獻(xiàn)［12］的Bluetooth4．1標(biāo)準(zhǔn)的能量模型，并假定每個(gè)節(jié)點(diǎn)中的初始能量為3J。能耗數(shù)據(jù)如圖4所示。可知，提出時(shí)隙分配算法有效地降低了總體能量，原因在于分配算法利用節(jié)點(diǎn)剩余能量構(gòu)建最小生成樹(shù)，再依據(jù)最小生成樹(shù)合理分配時(shí)隙，進(jìn)而降低了能耗。與TPO算法相比，提出的時(shí)隙分配算法的能耗平均降低了約5．4%。

4結(jié)論

本文針對(duì)無(wú)線傳感網(wǎng)絡(luò)的數(shù)據(jù)收集時(shí)延問(wèn)題，展開(kāi)研究，并提出新的時(shí)隙分配算法，進(jìn)而降低數(shù)據(jù)收集時(shí)延，同時(shí)減少節(jié)點(diǎn)能耗。利用克魯斯卡爾算法建立最小生成樹(shù)，再依據(jù)最小生成樹(shù)分配時(shí)隙。實(shí)驗(yàn)數(shù)據(jù)表明，提出的分配算法能夠合理地給節(jié)點(diǎn)分配時(shí)隙，并減少了節(jié)點(diǎn)能耗。

作者：白秋產(chǎn) 王亮明 單位：淮陰工學(xué)院