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

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

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

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

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

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

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

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