無(wú)線傳感器網(wǎng)絡(luò)可分負(fù)載調(diào)度研究.pdf

1、無(wú)線傳感器網(wǎng)絡(luò)的發(fā)展以及對(duì)其應(yīng)用需求的持續(xù)增長(zhǎng),不斷給調(diào)度問(wèn)題賦予新的內(nèi)涵并且提出新的挑戰(zhàn),任務(wù)調(diào)度一直是無(wú)線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)問(wèn)題。
　　 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限,所以其任務(wù)調(diào)度算法應(yīng)保證任務(wù)在最短的時(shí)間內(nèi)完成,以便用戶能夠根據(jù)采集的數(shù)據(jù)對(duì)監(jiān)控區(qū)域做出及時(shí)有效的判斷及響應(yīng),同時(shí)應(yīng)該減少節(jié)點(diǎn)能耗,延長(zhǎng)網(wǎng)絡(luò)壽命。用于無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度應(yīng)用建模的工具通常是有向無(wú)環(huán)圖(DAG)和獨(dú)立任務(wù)集。在一般情況下,基于這兩類模型的調(diào)度

2、問(wèn)題都是NP完全的?？煞重?fù)載理論在無(wú)線傳感器網(wǎng)絡(luò)上的應(yīng)用為其任務(wù)調(diào)度提供了一個(gè)有效的解決方案。與其它無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度問(wèn)題的啟發(fā)式解決方案不同,該技術(shù)不僅可以得到最優(yōu)解,而且可以得到解析解,從而保證了調(diào)度結(jié)果的一致性。本文研究了可分負(fù)載理論在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用技術(shù),具體研究成果如下:
　　 1.研究了異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)在分群結(jié)構(gòu)下的任務(wù)調(diào)度問(wèn)題。現(xiàn)有的基于可分負(fù)載理論的無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度模型都是在單層樹(shù)狀拓?fù)?或者同

3、構(gòu)的分群結(jié)構(gòu)這些特殊的網(wǎng)絡(luò)環(huán)境下進(jìn)行研究的。這些對(duì)網(wǎng)絡(luò)的假設(shè)條件并不適合于無(wú)線傳感器網(wǎng)絡(luò)的研究發(fā)展。本文分別在單信道、多信道以及有協(xié)處理器三種條件下,分析了分群結(jié)構(gòu)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的任務(wù)調(diào)度問(wèn)題。給出了異構(gòu)網(wǎng)絡(luò)環(huán)境下最短的總?cè)蝿?wù)完成時(shí)間和最優(yōu)任務(wù)調(diào)度方案的解析解,分析了任務(wù)調(diào)度的極限情況。并針對(duì)群首存儲(chǔ)資源有限的情況,給出了任務(wù)調(diào)度的線性規(guī)劃模型,分析其最優(yōu)解的情況。
　　 2.研究了無(wú)線傳感器網(wǎng)絡(luò)多輪任務(wù)調(diào)度問(wèn)題?？煞重?fù)載調(diào)

4、度算法分為單輪調(diào)度算法和多輪調(diào)度算法兩大類。單輪調(diào)度算法較為簡(jiǎn)單,但其計(jì)算和通信的重疊性比較差,額外的開(kāi)銷相對(duì)較大。多輪調(diào)度算法具有較好的計(jì)算和通信重疊性,從而降低整個(gè)應(yīng)用的響應(yīng)時(shí)間,降低了調(diào)度的額外開(kāi)銷。但由于比較難以分析等原因,使得對(duì)多輪調(diào)度算法的研究成果相對(duì)較少,已有的可分負(fù)載多輪調(diào)度算法大多數(shù)是基于同構(gòu)集群計(jì)算環(huán)境設(shè)計(jì)的,并且忽略處理結(jié)果的返回問(wèn)題。本文提出了分群結(jié)構(gòu)下,基于可分負(fù)載理論的無(wú)線傳感器網(wǎng)絡(luò)多輪任務(wù)調(diào)度算法。算法根據(jù)

5、各個(gè)群的任務(wù)處理速率按多輪方案將總?cè)蝿?wù)從SINK節(jié)點(diǎn)下發(fā)給各個(gè)群。為了去除由節(jié)點(diǎn)間通信干擾導(dǎo)致的性能下降,SINK節(jié)點(diǎn)相繼向各個(gè)群首發(fā)送每一輪的負(fù)載。每一輪各個(gè)群執(zhí)行完數(shù)據(jù)采集任務(wù)并把數(shù)據(jù)融合后,也由群首將該輪數(shù)據(jù)相繼向SINK節(jié)點(diǎn)報(bào)告,使得任務(wù)執(zhí)行和通信更好地重疊,最終減少了整個(gè)應(yīng)用的響應(yīng)時(shí)間且提高了網(wǎng)絡(luò)資源利用率。
　　 3.研究了無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度的博弈算法。在一個(gè)大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)中,組成系統(tǒng)的各個(gè)節(jié)點(diǎn)可以是屬于

6、不同公司、研究機(jī)構(gòu)甚至是個(gè)人的傳感器網(wǎng)絡(luò)或單個(gè)傳感器。因此每個(gè)節(jié)點(diǎn)都希望能夠最大化他們自己的利益。也就是說(shuō),每個(gè)傳感節(jié)點(diǎn)都是理性且自私的。傳感器節(jié)點(diǎn)可能原因能量限制而拒絕盡力地協(xié)作完成任務(wù),針對(duì)于傳感器節(jié)點(diǎn)存在這種潛在的自私行為,提出了一種無(wú)線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度的非合作博弈算法。通過(guò)對(duì)傳感器節(jié)點(diǎn)的自私行為引入懲戒機(jī)制,從而降低了節(jié)點(diǎn)背離協(xié)作的可能性。設(shè)計(jì)了一個(gè)與總?cè)蝿?wù)完成時(shí)間和節(jié)點(diǎn)所分配任務(wù)大小有關(guān)的效用函數(shù),證明了納什均衡的存在性。<

7、br>　　 4.提出了多SINK架構(gòu)的無(wú)線傳感器任務(wù)調(diào)度算法。多SINK的無(wú)線傳感器網(wǎng)絡(luò)比傳統(tǒng)架構(gòu)具有更好的穩(wěn)定性和有效性,是當(dāng)前一個(gè)研究熱點(diǎn)。算法將總?cè)蝿?wù)從多個(gè)SINK節(jié)點(diǎn)下發(fā)至網(wǎng)絡(luò)中。群內(nèi)節(jié)點(diǎn)在收到各個(gè)SINK的子任務(wù)后,同時(shí)開(kāi)始采集數(shù)據(jù),然后將結(jié)果相繼向群首報(bào)告。群首將群內(nèi)節(jié)點(diǎn)報(bào)告的數(shù)據(jù)融合后,相繼向各個(gè)SINK傳送結(jié)果,使得任務(wù)執(zhí)行和通信能夠更好的重疊,從而提高資源利用率和減少總?cè)蝿?wù)完成時(shí)間。
　　 5.提出了與可分負(fù)