無(wú)線傳感網(wǎng)絡(luò)中的有效連接調(diào)節(jié)-智能與網(wǎng)絡(luò)化系統(tǒng)研究所

1、無(wú)線傳感網(wǎng)絡(luò)中的有效連接調(diào)節(jié)摘要:在無(wú)線傳感網(wǎng)絡(luò)中，給一個(gè)源點(diǎn)|終點(diǎn)集合對(duì)，我們?cè)鯓诱{(diào)節(jié)才能使數(shù)據(jù)包在無(wú)線網(wǎng)絡(luò)中有效的從源頭傳遞到相應(yīng)目的地呢?其實(shí)存在很多因素影響著這個(gè)問(wèn)題，而且由于在無(wú)線傳感網(wǎng)絡(luò)中存在著干擾也使得這個(gè)問(wèn)題變得不簡(jiǎn)單。在這篇文章中我主要集中于尋找一個(gè)在無(wú)線有干擾的傳感網(wǎng)絡(luò)中有效的節(jié)點(diǎn)調(diào)節(jié)算法。關(guān)鍵字：節(jié)點(diǎn)，調(diào)節(jié)，無(wú)線傳感網(wǎng)絡(luò)。1、引言 無(wú)處不在的通信需求驅(qū)使著各種是通信變得方便的無(wú)線設(shè)備的發(fā)展。這種裝置，根據(jù)不同的規(guī)模和加工的限制，可以形成一個(gè)網(wǎng)絡(luò)的傳感節(jié)點(diǎn)，監(jiān)測(cè)活動(dòng)和收集數(shù)據(jù)或共享帶寬和能源資源促進(jìn)彼此溝通。我們面臨的挑戰(zhàn)在于設(shè)計(jì)這樣的網(wǎng)絡(luò)，以確保高效率利用有限的寬帶和電力

2、資源。雖然特設(shè)無(wú)線網(wǎng)絡(luò)可以提供方便的基礎(chǔ)設(shè)施，自由的溝通，我們被這種節(jié)點(diǎn)相距甚遠(yuǎn)而能夠同時(shí)傳輸這一實(shí)事所限制。 正如我們知道，數(shù)據(jù)包路由和調(diào)度是在控制和設(shè)計(jì)包交換網(wǎng)絡(luò)中常出現(xiàn)的關(guān)鍵問(wèn)題。在一個(gè)網(wǎng)絡(luò)中要發(fā)送一個(gè)數(shù)據(jù)包由源到目的地，則需要選擇一條路徑；一旦所有數(shù)據(jù)包的路徑已被決定，我們留下的問(wèn)題調(diào)節(jié)路徑上的數(shù)據(jù)。如果有多個(gè)數(shù)據(jù)包同時(shí)到達(dá)某個(gè)節(jié)點(diǎn)，他們必須被安排好或進(jìn)行排隊(duì)。在大多數(shù)情況下一個(gè)給定的數(shù)據(jù)包能夠在邊緣時(shí)刻被發(fā)送（有時(shí)靠近邊緣時(shí)不能同時(shí)通過(guò)）和調(diào)度問(wèn)題是決定在一個(gè)節(jié)點(diǎn)的數(shù)據(jù)包哪些應(yīng)該被發(fā)送。 由于特設(shè)路由要求節(jié)點(diǎn)合作，以推動(dòng)彼此的數(shù)據(jù)包通過(guò)網(wǎng)絡(luò)。這意味吞吐量在每一個(gè)節(jié)點(diǎn)的應(yīng)用是有限的，不

3、僅因?yàn)樵诺廊萘?，而且還由遠(yuǎn)程節(jié)點(diǎn)負(fù)責(zé)轉(zhuǎn)發(fā)。這種效應(yīng)可能會(huì)限制效用特設(shè)路由。因此，在本文中，我們考慮網(wǎng)絡(luò)通訊問(wèn)題:給定一個(gè)源-終點(diǎn)集合對(duì)，我們?cè)鯓诱{(diào)節(jié)才能是數(shù)據(jù)包在無(wú)線傳感網(wǎng)絡(luò)中有效的從源頭傳遞到目的地呢？最主要的影響因素是干擾，而且由于無(wú)線網(wǎng)絡(luò)中的干擾使得問(wèn)題變得棘手，下一步要考慮的其他因素則為公平和能源限制等等。 在本文中，我們側(cè)重于無(wú)線傳感網(wǎng)絡(luò)干涉問(wèn)題的鏈接調(diào)度算法。2、相關(guān)工作鏈路調(diào)度算法的分析，古普塔和庫(kù)馬爾1假設(shè)隨機(jī)通信模式并表明在ad hoc網(wǎng)絡(luò)中一個(gè)n個(gè)隨機(jī)節(jié)點(diǎn)中每個(gè)節(jié)點(diǎn)的能力都可以由一個(gè)幾何分析得出。它們還顯示出一個(gè)實(shí)現(xiàn)這一計(jì)劃的全球鏈接調(diào)度。謝潑德【2】認(rèn)為大量的發(fā)送信息而

4、產(chǎn)生的干擾影響了總?cè)萘浚ňW(wǎng)絡(luò)的可擴(kuò)展性。他指出說(shuō)的容量可以增加采用最小能量路由，并提出了一個(gè)有效的分布式信道接入技術(shù)。grossglauser和謝【3】考慮ad hoc網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)，表示每個(gè)節(jié)點(diǎn)在長(zhǎng)期其吞吐量能夠保持不變 網(wǎng)絡(luò)節(jié)點(diǎn)在移動(dòng)過(guò)程是變化但統(tǒng)一分配的固定網(wǎng)路?；舅枷胧且粋€(gè)源節(jié)點(diǎn)的數(shù)據(jù)包分發(fā)到盡量多的不同節(jié)點(diǎn)。在數(shù)據(jù)包可以到達(dá)或靠近目的地時(shí)這些節(jié)點(diǎn)發(fā)放數(shù)據(jù)包。因此，預(yù)計(jì)路徑長(zhǎng)度為一個(gè)固定的常數(shù)。盡管如此，這種結(jié)果嚴(yán)格依賴于流動(dòng)模式。進(jìn)一步說(shuō)，保證固定吞吐量只取得了長(zhǎng)時(shí)間的框架。這一結(jié)果，然而，提出了一種利用節(jié)點(diǎn)運(yùn)動(dòng)在從應(yīng)用程序中傳送數(shù)據(jù)包時(shí)可以忍受長(zhǎng)時(shí)間拖延的方法。一些現(xiàn)有的研究

5、主要集中在公平的802.11的背景下特設(shè)轉(zhuǎn)發(fā)。nandagopal等人4提出了一種算法，給網(wǎng)絡(luò)中的每個(gè)數(shù)據(jù)流公平等量的空間，即使與其他資源相比有更多爭(zhēng)議考慮。羅等人。【5】提出了一種算法，以上每一個(gè)流動(dòng)的公平的共享資源，使整個(gè)網(wǎng)絡(luò)達(dá)到最大化從而提供更多機(jī)會(huì)流動(dòng)從而減少傳輸造成的干擾。那個(gè)算法可以改善802.11特設(shè)轉(zhuǎn)發(fā)效率。 鏈接調(diào)度算法護(hù)理的問(wèn)題與收集的來(lái)源與目的地對(duì)我們?nèi)绾伟才艛?shù)據(jù)包在無(wú)線網(wǎng)絡(luò)中的傳輸使得其能有效的從源頭傳送到相應(yīng)目的地，這樣一個(gè)鏈接調(diào)度問(wèn)題類似最高流動(dòng)問(wèn)題(mcfp)，這種不同于的傳統(tǒng)無(wú)線傳感器網(wǎng)絡(luò)中遇到的問(wèn)題，對(duì)于無(wú)線分組調(diào)度傳感器網(wǎng)絡(luò)，海德等。【6】研究了無(wú)線網(wǎng)絡(luò)中權(quán)

6、衡擠塞，擴(kuò)張和能源之間路由算法的的最壞情況，在磁盤圖模型與d2型邊緣干擾限制。他們還提供在線和離線路由算法針對(duì)于端到端分組調(diào)度的問(wèn)題。然而，調(diào)度算法【6】可有一個(gè)近似比為的最壞情況。距離2干涉模型介質(zhì)訪問(wèn)控制層分組調(diào)度的ad-hoc網(wǎng)絡(luò)已審議。這個(gè)問(wèn)題可以投任為一節(jié)點(diǎn)或邊緣色素視決定于設(shè)置【10】。每個(gè)數(shù)據(jù)包一次一個(gè)邊的經(jīng)典模型中，其中一項(xiàng)最重要的結(jié)果就是是里頓成果等?！?1】其中表明存在一個(gè)常數(shù)逼近因子，使用本地引理。其結(jié)果假定數(shù)據(jù)包已經(jīng)帶有預(yù)定指定的路徑。這個(gè)工作成果隨之而來(lái)的一系列文件，不斷改善其性能或復(fù)雜度（見【12】。拉巴尼和tardos13提供 分布式算法對(duì)于這個(gè)問(wèn)題，這是改善夫斯

7、基和拉巴尼【14】。3、預(yù)備工作 在本文中，我們基于分析容量的基礎(chǔ)上，我們重點(diǎn)于連接調(diào)度算法。所有的分析基于 靜態(tài)ad hoc網(wǎng)絡(luò)，因?yàn)椋诖蠖鄶?shù)流動(dòng)情況下，在數(shù)據(jù)交換時(shí)節(jié)點(diǎn)并不移動(dòng)很大的距離，可以視移動(dòng)網(wǎng)絡(luò)為靜態(tài)的。 本節(jié)包含的基本定義和概念用于論文的后文。我們考慮多跳無(wú)線網(wǎng)絡(luò)。該網(wǎng)路由一個(gè)直方圖直接確定。節(jié)點(diǎn)圖對(duì)應(yīng)于個(gè)別收發(fā)器和一個(gè)指示邊緣意味著可以直接有傳播到。a調(diào)節(jié)描述在某一時(shí)刻對(duì)應(yīng)的通過(guò)節(jié)點(diǎn)的數(shù)據(jù)量，圖中t表示調(diào)節(jié)時(shí)間段，而則是直接變量有以下定義范圍: a調(diào)節(jié)s是在0-1轉(zhuǎn)讓給變量。本文中我們側(cè)重于定期安排，a調(diào)節(jié)s是按周期為t周期間接性的。我們有。在無(wú)線網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)沒(méi)受到干擾時(shí)可

8、以同時(shí)進(jìn)行傳遞插槽。 我們假設(shè)，頂點(diǎn)嵌入在平面。每一個(gè)節(jié)點(diǎn)（收發(fā)器）有由指定的相應(yīng)的范圍。一個(gè)必要的（但不充分）條件對(duì)于收發(fā)器接受信號(hào)，而在定義范圍內(nèi)，具體的說(shuō)，如果傳輸從到不可行，也并不是在的定義范圍之外或者是其他原因（如與之間存在阻隔），然后邊緣沒(méi)有出現(xiàn)在圖。這是非常重要的對(duì)于顯示網(wǎng)絡(luò)模型諸如室內(nèi)無(wú)線網(wǎng)絡(luò)或者室外網(wǎng)絡(luò)存在的障礙物。我們只考慮全方位定向天線和定向天線是省略了。由于傳輸媒介的無(wú)線，同時(shí)因?yàn)榻吘墏鬏斂赡芑ハ喔蓴_造成的碰撞。形式上，我們說(shuō)邊緣相互干擾如果邊緣和不能成功傳遞在同一個(gè)時(shí)間跳躍點(diǎn)。讓指向邊緣集，這個(gè)集同時(shí)干擾著邊緣，當(dāng)邊緣在傳輸時(shí)則不能夠成功傳輸。在網(wǎng)絡(luò)中一種干擾模式限

9、制著包含邊的集。幾種如此的模式已經(jīng)被研究出來(lái)，因?yàn)榛炯夹g(shù)中的變化，協(xié)議等。例如，該議定書干擾模型【6】如說(shuō)明圖1，如果一個(gè)節(jié)點(diǎn)傳輸?shù)焦?jié)點(diǎn)，這種傳輸將被成功接收如果?；蚱渌麄鬏斊魇?。而且是協(xié)議規(guī)劃的保護(hù)區(qū)。以上的協(xié)議模型中，一個(gè)節(jié)點(diǎn)一次接受一條信息或者傳輸一條信息（而不是雙方）。因此對(duì)任何邊緣，或所有其他伴隨或是所有邊緣都包括在幾何中。4 、硬性問(wèn)題 鑒于網(wǎng)絡(luò)模型的指示圖，讓指一套邊緣集干擾邊，我們可以計(jì)算出任何在邊的干擾設(shè)置，由指出鏈流速度載體。這載體同伙鏈接率項(xiàng)（總率為所有流動(dòng)對(duì)鏈接）對(duì)每一個(gè)環(huán)節(jié)，恢復(fù) 為指標(biāo)變量，指出當(dāng)時(shí)鏈?zhǔn)欠癯晒鬟f。通過(guò)定義，當(dāng)， ,則有 。 不失概括性，時(shí)間劃分為

10、相同的毗連窗口或者長(zhǎng)度為w的幀，w為足夠長(zhǎng)的正值。（例如我們假設(shè)w滿足所有e，w x(e)是整數(shù)）。 考慮單個(gè)幀w，它的時(shí)間跳躍都被標(biāo)記為，對(duì)于每一個(gè)邊，其副程式定義的子集為 如下所述：1各個(gè)邊收到一個(gè)的時(shí)間跳躍片段。2 兩個(gè)邊緣相互干擾并沒(méi)有相同的交集。 有效節(jié)點(diǎn)調(diào)節(jié)問(wèn)題是找到最小這樣我們能夠最快的速度傳遞數(shù)據(jù)包。 定義：給定圖和干擾集 適用于所有 在中。有效節(jié)點(diǎn)調(diào)節(jié)就是要找出周邊子集合有 和 集合 是最小的。 在我們顯示有效鏈接問(wèn)題之前是np-完全，我們引進(jìn)一個(gè)眾所周知的問(wèn)題為圖距離-2-邊著色。讓為單數(shù)，不直接給出圖形。我們說(shuō)為的兩個(gè)邊緣在距離為2的范圍內(nèi)兩者有毗連或者有邊毗連他們。a距

11、離-2-邊-色彩中的是一個(gè)指定的變的顏色，所以任意連個(gè)邊在為2的距離內(nèi)兩者能夠被區(qū)分出來(lái)，或者等效于，一個(gè)頂點(diǎn)顏色在線性平面圖。如果色彩只有種，則說(shuō)為一個(gè)-2-邊-可色彩化。任何-2-邊-可色彩化圖同樣為+1-邊-可色彩化。a距離-2-邊-色彩同樣被認(rèn)為有強(qiáng)烈的邊緣色彩。mzhdian17證實(shí)，通過(guò)從圖-顏色-能力，由-完全 決定，對(duì)任何一個(gè)固定的g，是否一個(gè)雙圖形其周長(zhǎng)為應(yīng)有一個(gè)深的色彩且. 在圖距離-2-邊-顏色中很容易看出有效調(diào)節(jié)問(wèn)題的簡(jiǎn)單形式，所以有效節(jié)點(diǎn)調(diào)節(jié)問(wèn)題是np-難度。5、鏈路的調(diào)節(jié)算法 本文中我既有中心和分布式的算法調(diào)節(jié)基于著作【18】。算法運(yùn)行如下：時(shí)間被劃分為等量且毗連窗

12、口或者為長(zhǎng)度為w的幀，幀為足夠大的正值（例如我們假設(shè)w滿足左右，是正值）。算法引入一個(gè)子集為幀-調(diào)節(jié)并且具體到每一個(gè)幀的每個(gè)邊.，這種調(diào)節(jié)被周期重復(fù)對(duì)于每個(gè)幀從而獲得最終的安排。我們現(xiàn)在來(lái)詳細(xì)描述幀-調(diào)節(jié)算法，它的偽代碼是算法1中提及過(guò)。 考慮單個(gè)幀w時(shí)，它的時(shí)間跳躍點(diǎn)標(biāo)記為。對(duì)于每一個(gè)邊，其副程式指定一個(gè)子集 例如如下： 1、各個(gè)邊接收到槽值點(diǎn)。 2、 兩個(gè)邊緣相互干擾而且其沒(méi)有指定相同的時(shí)間跳躍點(diǎn)。對(duì)于所有的，集(中的時(shí)間槽點(diǎn)集，其能準(zhǔn)確的指向)被初始化為空集。中的邊被有序的處理在沒(méi)有長(zhǎng)度增長(zhǎng)指令情況下。即時(shí)邊被處理為。在中讓有向指向時(shí)間槽點(diǎn)數(shù)其在中已經(jīng)指向邊緣（這樣就不能指派給）； 。在

13、剩下的節(jié)點(diǎn) ，我們選擇子集，時(shí)間點(diǎn)并使之指向 算法1 進(jìn)度（）1：對(duì)所有有2： = 3：結(jié)束4：在沒(méi)有長(zhǎng)度增長(zhǎng)指令時(shí)5：對(duì)時(shí)6：7 8：=任意大小為子集9：結(jié)束圖2. 鏈接調(diào)節(jié)算法 下一步我們推出一個(gè)同步分散執(zhí)行的中心化算法，其決定于周圍的數(shù)量。這種分散算法是基于對(duì)區(qū)域【15，16】描述的思想，假設(shè)網(wǎng)絡(luò)中對(duì)每一個(gè)時(shí)間窗口中時(shí)間插槽點(diǎn)數(shù)是有個(gè)目標(biāo)的，算法與這想法的區(qū)別在于邊緣被量化而且槽值數(shù)是按照量化比例來(lái)定的。在分散算法中偽代碼出現(xiàn)在算法2中。重新啟用指向傳輸信號(hào)的范圍。讓指向左右的節(jié)點(diǎn)集則能在網(wǎng)絡(luò)中能夠潛在的影響.我們說(shuō)節(jié)點(diǎn)已經(jīng)完成當(dāng)相關(guān)邊緣的槽點(diǎn)都被選中時(shí)。分散算法循環(huán)執(zhí)行，一個(gè)節(jié)點(diǎn)的最大射線并沒(méi)縮減完成，每周期算法都有較高概率，以下為分散算法2.分布算法21：對(duì)所有2：= 3：結(jié)束4：對(duì)每個(gè)周期5：對(duì)每個(gè)還沒(méi)結(jié)束的節(jié)點(diǎn)，如果有還沒(méi)有結(jié)束，則不在這個(gè)周期內(nèi)。則有的可能成為備選，為中未完成的節(jié)點(diǎn)數(shù)。6：如果被選為備選，而且有則也被選為備選，不出現(xiàn)在此周期中。7：如果出現(xiàn)在此次周