間歇性分割的自組織網(wǎng)絡(luò)路由算法和節(jié)點(diǎn)移動(dòng)模型研究中文摘要

在移動(dòng)自組織網(wǎng)絡(luò)的一些應(yīng)用中，節(jié)點(diǎn)的快速移動(dòng)等原因通常導(dǎo)致網(wǎng)絡(luò)呈間歇性分割，此時(shí)常規(guī)的Ad hoc路由協(xié)議效率低下甚至無(wú)效，網(wǎng)絡(luò)的可存活性面臨著嚴(yán)峻的挑戰(zhàn)。本項(xiàng)目研究間歇性分割的移動(dòng)自組織網(wǎng)絡(luò)的路由算法、節(jié)點(diǎn)移動(dòng)模型及其相關(guān)理論。采用網(wǎng)絡(luò)編碼增加在冗余路徑上的信息轉(zhuǎn)發(fā)，提出具有抗毀能力的彈性路由算法；針對(duì)網(wǎng)絡(luò)的間歇性分割問(wèn)題，提出一種新穎的基于多維虛擬空間網(wǎng)格的網(wǎng)絡(luò)拓?fù)浞指顧z測(cè)算法和節(jié)點(diǎn)移動(dòng)預(yù)測(cè)模型，為路由選擇提供有效、合理的判據(jù)，提高間歇性分割的移動(dòng)自組織網(wǎng)絡(luò)的可存活性和抗毀能力；借鑒信息論的有噪信道模型和信道編碼理論，研究拓?fù)淇熳兦议g歇性分割網(wǎng)絡(luò)的路由技術(shù)，提出新的基于網(wǎng)絡(luò)編碼的不確定性路由轉(zhuǎn)發(fā)的信道模型和理論，推動(dòng)網(wǎng)絡(luò)信息論的研究和發(fā)展。 2100433B

路由算法，又名選路算法，可以根據(jù)多個(gè)特性來(lái)加以區(qū)分。算法的目的是找到一條從源路由器到目的路由器的“好”路徑（即具有最低費(fèi)用的路徑） 。算法設(shè)計(jì)者的特定目標(biāo)影響了該路由協(xié)議的操作；具體來(lái)說(shuō)存在著多種路由算法，每種算法對(duì)網(wǎng)絡(luò)和路由器資源的影響都不同；由于路由算法使用多種度量標(biāo)準(zhǔn)（metric），從而影響到最佳路徑的計(jì)算。路由算法通常具有下列設(shè)計(jì)目標(biāo)的一個(gè)或多個(gè)：優(yōu)化、簡(jiǎn)單、低耗、健壯、穩(wěn)定、快速聚合、靈活性。（1）最優(yōu)化：指路由算法選擇最佳路徑的能力。根據(jù)metric的值和權(quán)值來(lái)計(jì)算。（2）簡(jiǎn)潔性：算法設(shè)計(jì)必須簡(jiǎn)潔。路由協(xié)議在網(wǎng)絡(luò)中必須高效地提供其功能，盡量減少軟件和應(yīng)用的開(kāi)銷(xiāo)。這在當(dāng)實(shí)現(xiàn)路由算法的軟件必須運(yùn)行在物理資源有限的計(jì)算機(jī)上時(shí)尤其重要。（3）堅(jiān)固性：路由算法處于非正?；虿豢深A(yù)料的環(huán)境時(shí)，如硬件故障、負(fù)載過(guò)高或操作失誤時(shí)，都能正確運(yùn)行。由于路由器分布在網(wǎng)絡(luò)聯(lián)接點(diǎn)上，所以在它們出故障時(shí)會(huì)產(chǎn)生嚴(yán)重后果。最好的路由器算法通常能經(jīng)受時(shí)間的考驗(yàn)，并在各種網(wǎng)絡(luò)環(huán)境下被證實(shí)是可靠的。（4）快速收斂：收斂是在最佳路徑的判斷上所有路由器達(dá)到一致的過(guò)程。當(dāng)某個(gè)網(wǎng)絡(luò)事件引起路由可用或不可用時(shí)，路由器就發(fā)出更新信息。路由更新信息遍及整個(gè)網(wǎng)絡(luò)，引發(fā)重新計(jì)算最佳路徑，最終達(dá)到所有路由器一致公認(rèn)的最佳路徑。收斂慢的路由算法會(huì)造成路徑循環(huán)或網(wǎng)絡(luò)中斷。（5）靈活性：路由算法要求可以快速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境。例如，某個(gè)網(wǎng)段發(fā)生故障，路由算法要能很快發(fā)現(xiàn)故障，并為使用該網(wǎng)段的所有路由選擇另一條最佳路徑。2100433B

可以看到，在LS和DV算法中，每個(gè)路由器都需要保存其他路由器的一些信息。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，網(wǎng)絡(luò)中的路由器也將增加。因此，路由表的規(guī)模也將增大，從而使路由器不能有效地處理網(wǎng)絡(luò)流量。使用分級(jí)路由可以解決這個(gè)問(wèn)題。讓使用DV算法來(lái)查找節(jié)點(diǎn)間的最佳路由。

在下述情形中，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)保存了一個(gè)有17個(gè)記錄的路由表。在分級(jí)路由中，路由器被分成很多組，稱(chēng)為區(qū)域。每個(gè)路由器都只有自己所在區(qū)域路由器的信息，而沒(méi)有其他區(qū)域路由器的信息。所以在其路由表中，路由器只需要存儲(chǔ)其他每個(gè)區(qū)域的一條記錄。在這個(gè)例子中，我們將網(wǎng)絡(luò)分為5個(gè)區(qū)域。

如果A想發(fā)送分組數(shù)據(jù)包到在區(qū)域2中的一個(gè)路由器（D、E、F或G），它就將分組數(shù)據(jù)包先發(fā)送到B，依此類(lèi)推?？梢钥吹剑谶@種類(lèi)型的路由中，可以對(duì)路由表進(jìn)行概括，因此網(wǎng)絡(luò)效率提高了。上面的例子描述了一個(gè)兩級(jí)的分級(jí)路由。同樣我們也可以采用三級(jí)或者四級(jí)的分級(jí)路由。

在一個(gè)三級(jí)的分級(jí)路由中，網(wǎng)絡(luò)被分為很多簇。每個(gè)簇由很多個(gè)區(qū)域組成，每個(gè)區(qū)域包含很多個(gè)路由器。分級(jí)路由廣泛應(yīng)用于互聯(lián)網(wǎng)路由中，并且使用了多種路由協(xié)議。

本課題以無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)跟蹤為背景，研究節(jié)能的目標(biāo)跟蹤協(xié)議和算法，解決目前目標(biāo)跟蹤協(xié)議存在通信量大、參與跟蹤的節(jié)點(diǎn)數(shù)目多從而導(dǎo)致耗能多的問(wèn)題。具體研究無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤機(jī)制，節(jié)點(diǎn)感應(yīng)度計(jì)算模型，并研究基于節(jié)點(diǎn)感應(yīng)度的目標(biāo)定位與跟蹤算法。 本項(xiàng)目提出了一種節(jié)點(diǎn)感應(yīng)度計(jì)算模型，該模型主要利用傳感器節(jié)點(diǎn)感應(yīng)到的信號(hào)強(qiáng)度與離目標(biāo)的距離互相關(guān)特性，即感應(yīng)到的信號(hào)強(qiáng)度越大，則感應(yīng)度值越高。感應(yīng)度值將作為跟蹤過(guò)程中節(jié)點(diǎn)是否參與跟蹤的依據(jù)之一。提出了基于多邊形的目標(biāo)跟蹤框架-FaceTrack,該跟蹤框架包括目標(biāo)在多邊形區(qū)域之間的穿越過(guò)程中目標(biāo)跟蹤方法，節(jié)點(diǎn)喚醒與休眠時(shí)機(jī)、主跟蹤節(jié)點(diǎn)的選擇方法等。模擬結(jié)果表明，F(xiàn)aceTrack跟蹤框架能有效定位目標(biāo)所在多邊形區(qū)域。為了提高跟蹤精度，即實(shí)現(xiàn)目標(biāo)在多邊形內(nèi)部動(dòng)態(tài)移動(dòng)的跟蹤與定位，本項(xiàng)目以節(jié)點(diǎn)感應(yīng)度模型為基礎(chǔ)，提出了一種節(jié)點(diǎn)自主決策是否參與跟蹤的目標(biāo)跟蹤算法（NS-ADTT），該算法基于定位邊采用加權(quán)質(zhì)心算法對(duì)目標(biāo)位置進(jìn)行估計(jì)，并且，節(jié)點(diǎn)可根據(jù)自身感應(yīng)度值及局部網(wǎng)絡(luò)情況自主決策是否參與當(dāng)前跟蹤。仿真結(jié)果表明，在目標(biāo)跟蹤過(guò)程中，該算法在保證一定跟蹤精度的基礎(chǔ)上減少了參與跟蹤的節(jié)點(diǎn)數(shù)， 降低了網(wǎng)絡(luò)能耗，有效地延長(zhǎng)了網(wǎng)絡(luò)生命周期。 本項(xiàng)目對(duì)其他跟蹤模式進(jìn)行了探索，基于拍賣(mài)的思想，提出了基于拍賣(mài)的目標(biāo)跟蹤算法Auction-Based Adaptive Sensor Activation Algorithm(簡(jiǎn)稱(chēng)AASA)。拍賣(mài)機(jī)制讓預(yù)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)通過(guò)競(jìng)爭(zhēng)產(chǎn)生最適合參與目標(biāo)跟蹤的節(jié)點(diǎn)。拍賣(mài)過(guò)程充分考慮了節(jié)點(diǎn)的剩余能量以及節(jié)點(diǎn)到目標(biāo)預(yù)測(cè)距離。模擬結(jié)果表明,算法AASA在保持可接受跟蹤質(zhì)量的前提下,能有效地解決能量消耗不平衡的問(wèn)題。