本文選題：信息物理融合系統(tǒng)　切入點：占空比傳感器網(wǎng)絡(luò)　出處：《哈爾濱工業(yè)大學(xué)》2017年博士論文　論文類型：學(xué)位論文

【摘要】：信息物理融合系統(tǒng)是一種集計算、通信、感知和控制等功能為一體的大規(guī)模分布式異構(gòu)系統(tǒng),主要由傳感器網(wǎng)絡(luò)、執(zhí)行組件、控制器和網(wǎng)關(guān)設(shè)備等構(gòu)成。由于其能夠?qū)ξ锢硎澜绺咝崟r、分布協(xié)同、安全可靠地感知和控制,實現(xiàn)信息世界與物理世界的高度融合,目前已經(jīng)在國防軍事和社會生活中得到了廣泛地應(yīng)用。在信息物理融合系統(tǒng)中,傳感器網(wǎng)絡(luò)通過協(xié)作地采集、感知和計算之后將采集到的信息以多跳傳輸方式發(fā)送給用戶和終端,然后用戶和終端根據(jù)采集到的信息生成相應(yīng)的反饋控制命令。在這其中,感知數(shù)據(jù)的實時傳輸和調(diào)度至關(guān)重要。例如,在戰(zhàn)場上的目標探測與追蹤、醫(yī)療救護以及化學(xué)放射性元素檢測和預(yù)防等系統(tǒng)中,控制信息或關(guān)鍵數(shù)據(jù)必須在限制的時間內(nèi)到達用戶和終端,以便系統(tǒng)及時作出反應(yīng)從而避免災(zāi)難性的后果。另一方面,當傳感器節(jié)點要求工作在占空比模式來節(jié)省能耗和延長網(wǎng)絡(luò)生存周期時,數(shù)據(jù)傳輸?shù)难舆t將會急劇增加。在這種網(wǎng)絡(luò)中,實時數(shù)據(jù)傳輸與調(diào)度問題變得更為復(fù)雜,但是目前此類問題研究較少。因此,本文將主要對占空比網(wǎng)絡(luò)中的實時數(shù)據(jù)傳輸與調(diào)度等問題展開研究。首先,本文研究了信息物理融合系統(tǒng)中實時端到端數(shù)據(jù)傳輸?shù)穆酚伤惴ㄔO(shè)計問題。實時路由是信息物理融合系統(tǒng)中非常重要的一個服務(wù),是很多應(yīng)用的基礎(chǔ)。為了實現(xiàn)占空比傳感器網(wǎng)絡(luò)中任意端到端之間的實時數(shù)據(jù)傳輸,本文提出了一種基于動態(tài)切換的實時路由算法(DSRT)。針對占空比網(wǎng)絡(luò)中睡眠延遲太大的特點,DSRT首先利用2跳鄰居信息提出了一種可達速度的概念來幫助發(fā)現(xiàn)延遲更優(yōu)的路徑(實驗證明該方法至少能夠發(fā)現(xiàn)20%左右延遲更優(yōu)的路徑)。另外,本文首次發(fā)現(xiàn)在占空比網(wǎng)絡(luò)中節(jié)點的擁塞程度不僅與緩沖隊列中數(shù)據(jù)包的個數(shù)有關(guān),而且與數(shù)據(jù)包的目的節(jié)點有關(guān)。然而傳統(tǒng)的方法無法區(qū)分此類擁塞,因此DSRT利用動態(tài)切換機制提出了一種通過將緩沖隊列分類的擁塞避免算法。另外,考慮到傳感器節(jié)點在無線傳輸時鏈路非常不可靠的特點,本文還提出了一種基于擴展活動時間槽的實時路由算法(RRAD)。在RRAD算法中,本文利用擴展活動時間槽和ARQ-based傳輸機制將數(shù)據(jù)包的延遲降低了1倍以上。另外,RRAD針對占空比網(wǎng)絡(luò)中節(jié)點異步醒來的特點,提出了一種輕量級的潛在轉(zhuǎn)發(fā)節(jié)點選擇算法。該算法能夠給節(jié)點提供一次額外的轉(zhuǎn)發(fā)機會。大量的模擬實驗驗證了本文提出的DSRT和RRAD算法在路由延遲和可靠性方面的高效性能。其次,本文研究了信息物理融合系統(tǒng)中節(jié)能及延遲受限的多播調(diào)度問題。在信息物理融合系統(tǒng)中,多播路由是提供一對多通信的一種基本服務(wù),即源節(jié)點同時將數(shù)據(jù)包發(fā)送到多個目的節(jié)點。然而,當傳感器節(jié)點工作在占空比模式時,發(fā)送節(jié)點需要傳輸多次以將相同的消息廣播給一組相鄰的節(jié)點,這使得最小能耗多播問題變得異常復(fù)雜。因此,本文研究了占空比傳感器網(wǎng)絡(luò)中的最小能耗多播問題,并證明了該問題是一個NP-hard問題。為了解決這一問題,本文提出了輔助圖的概念用于統(tǒng)一調(diào)度節(jié)點發(fā)射功率和發(fā)送時間槽以及構(gòu)建最小能耗多播樹,并提出了構(gòu)建輔助圖的貪心算法。基于上述輔助圖,本文提出了近似比為4lnK的近似調(diào)度與構(gòu)造算法,其中K是目標節(jié)點的數(shù)目。另一方面,由于占空比網(wǎng)絡(luò)中節(jié)點只能夠在其處于活動狀態(tài)時接收數(shù)據(jù)包,導(dǎo)致多播延遲異常高。但是,目前現(xiàn)有的算法均沒有考慮如何減小多播延遲,使其處于用戶預(yù)期之內(nèi)。因此,本文還研究了延遲受限的多播調(diào)度算法,通過在網(wǎng)絡(luò)中增加最少個數(shù)的活動時間槽來使得多播延遲小于用戶給定的延遲閾值。為了解決該問題,本文提出了一種動態(tài)規(guī)劃算法來優(yōu)化所需要增加活動時間槽的個數(shù)。理論分析和實驗結(jié)果驗證了本文提出的算法在減小能量消耗和傳輸冗余以及保證實時性方面的有效性。第三,本文研究了信息物理融合系統(tǒng)中最小延遲數(shù)據(jù)聚集調(diào)度問題。在信息物理融合系統(tǒng)中,數(shù)據(jù)聚集可以方便sink節(jié)點獲取整個網(wǎng)絡(luò)的摘要信息。而最小延遲數(shù)據(jù)聚集調(diào)度問題(MLAS),即尋求一個最快無沖突的聚集調(diào)度計劃,已經(jīng)受到了學(xué)者們的廣泛關(guān)注。但是當節(jié)點工作在占空比模式時,節(jié)點只能在活動狀態(tài)時接收數(shù)據(jù)包。在這種網(wǎng)絡(luò)中,利用網(wǎng)絡(luò)中有限的活動時間槽來減少延遲極為重要。但是現(xiàn)有的算法很少考慮這個問題,并且大都假設(shè)在聚集過程中采用固定的結(jié)構(gòu)來生成聚集樹,這無疑極大地限制了活動時間槽的利用率。因此,本文考慮了基于非固定結(jié)構(gòu)的MLAS問題。本文首次給出了占空比網(wǎng)絡(luò)中分布式聚集調(diào)度算法,該算法同時生成聚集樹和無沖突的聚集調(diào)度計劃。接著,本文理論證明了該算法的聚集延遲上界為(?),其中C表示占空比,ξ=|2π/arccos(1+1/ε)|,ε是[0.05,1]中的一個實數(shù),R表示網(wǎng)絡(luò)的半徑,?表示最大的度數(shù)。大量的模擬實驗證明本文提出的算法能夠?qū)⒒顒訒r間槽的利用率和聚集延遲改善1倍以上。最后,本文研究了信息物理融合系統(tǒng)中最小延遲信標調(diào)度問題。在信息物理融合系統(tǒng)中,信標調(diào)度要求每個節(jié)點在本地將信標包廣播給所有的鄰居節(jié)點。然而,在占空比網(wǎng)絡(luò)中,最小延遲信標調(diào)度問題缺乏研究。已有的工作均有非常強的假設(shè),即每個節(jié)點在一個工作周期內(nèi)只能醒來一次。為了適應(yīng)更普遍的情況,本文研究了占空比網(wǎng)絡(luò)中最小延遲信標調(diào)度問題,其中每個節(jié)點在一個工作周期內(nèi)可醒來多次,該問題被稱為MLBSDCA問題。本文首先提出了一種基于邊的調(diào)度框架。基于該框架提出了一種啟發(fā)式的調(diào)度算法來解決協(xié)議干擾模型下的MLBSDCA問題。接著,提出了一個具有(ρ+1)2·||近似比的近似算法來進一步降低信標延遲,其中ρ表示干擾半徑,|W|表示一個工作周期內(nèi)最多可允許活動時間槽的個數(shù)。當ρ和|W|等于1時,該算法的近似比為4,優(yōu)于以往算法的近似比10。另外,針對物理干擾模型下的MLBSDCA問題,本文提出了兩種近似算法,并且證明了其近似比。大量的模擬實驗證明本文提出的算法能夠?qū)⑿艠搜舆t降低2倍以上。
[Abstract]:......
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：TP212.9;TP301.6
，

本文編號：1572542