基于圖論的移動(dòng)Ad Hoc網(wǎng)絡(luò)分群算法研究.pdf

1、無(wú)線移動(dòng)Ad Hoc網(wǎng)絡(luò)是由一組帶有無(wú)線通信收發(fā)裝置的移動(dòng)終端節(jié)點(diǎn)組成的具有任意性和臨時(shí)性的無(wú)中心、網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)、自組網(wǎng)絡(luò)系統(tǒng)，每個(gè)節(jié)點(diǎn)既是主機(jī)又是路由器。移動(dòng)Ad Hoc網(wǎng)絡(luò)具有自組織、可移動(dòng)、多跳路由、展開(kāi)速度快、抗毀性強(qiáng)、不需要現(xiàn)有信息基礎(chǔ)設(shè)施的支持等特點(diǎn)。因此被應(yīng)用于軍事通信、傳感器網(wǎng)絡(luò)、緊急服務(wù)與災(zāi)難恢復(fù)、移動(dòng)網(wǎng)絡(luò)等領(lǐng)域。
　　 本文首先研究了移動(dòng)Ad Hoc網(wǎng)絡(luò)的特點(diǎn)、網(wǎng)絡(luò)的結(jié)構(gòu)、協(xié)議棧及相關(guān)問(wèn)題。由于移動(dòng)Ad Ho

2、c網(wǎng)絡(luò)與傳統(tǒng)網(wǎng)絡(luò)有著不同的特性，從而決定了它們的關(guān)鍵技術(shù)的差異性。根據(jù)移動(dòng)Ad Hoc網(wǎng)絡(luò)的結(jié)構(gòu)和特點(diǎn)，著重從它的特有的連通方式研究了移動(dòng)Ad Hoc網(wǎng)絡(luò)的拓?fù)湫纬伤惴?。Ad Hoc網(wǎng)絡(luò)的兩種拓?fù)浣Y(jié)構(gòu)中平面結(jié)構(gòu)比較簡(jiǎn)單，在平面結(jié)構(gòu)中所有節(jié)點(diǎn)的地位都是平等的功能也是相同的，原則上不會(huì)發(fā)生瓶頸問(wèn)題，相對(duì)比較安全。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)增多時(shí)，為了控制開(kāi)銷、提高網(wǎng)絡(luò)的可擴(kuò)展性，一般會(huì)選擇分級(jí)結(jié)構(gòu)，即尋求虛擬骨干網(wǎng)絡(luò)。Ad Hoc網(wǎng)絡(luò)生成的虛擬骨干網(wǎng)絡(luò)一般

3、采用樹(shù)形和群兩種結(jié)構(gòu)。
　　 其次，提出了采用圖論的方式生成Ad Hoc網(wǎng)絡(luò)的虛擬骨干網(wǎng)。在無(wú)線自組網(wǎng)中搜索主干節(jié)點(diǎn)和群首形成虛擬骨干網(wǎng)的過(guò)程類似于圖論中的最小連通支配集和最小支配集問(wèn)題的求解過(guò)程。在連通支配集算法求解的過(guò)程中，由于在獨(dú)立集的連通階段中新的支配節(jié)點(diǎn)的增加，使得算法在執(zhí)行過(guò)程中造成節(jié)點(diǎn)之間環(huán)路的生成，這樣就增加了冗余支配節(jié)點(diǎn)的生成幾率，也增大了主干網(wǎng)的維護(hù)成本。本文采用回饋的思想，限制其環(huán)路的出現(xiàn)，從而減少網(wǎng)關(guān)節(jié)點(diǎn)