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

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

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

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