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

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

本文編號(hào)：1572542