【正文】 用鏈路沖突圖性質(zhì)的分布式極大團構(gòu)造方法。但是現(xiàn)在已有的求極大團的算法都是集中式的，不能夠直接在我們的信道分配方案中應(yīng)用。而在每個極大團中，用以負載為度量標準的貪心算法來進行信道分配。還有一種情況就是類似如和這種鏈路它們雖然也同時處于不同的極大團和中，但它們也同時都在團和中，所以它們之間進行數(shù)據(jù)傳輸是會互相沖突的。即在極大團中的鏈路和、不能同時進行數(shù)據(jù)傳輸，否則將會發(fā)生沖突。在假設(shè)發(fā)送半徑和干擾半徑相同的情況下，上一節(jié)中的網(wǎng)絡(luò)拓撲圖形成的鏈路沖突圖有三個極大團，分別為，和。所以在沖突圖中，每個極大團可以看作是一個獨立的信道資源競爭區(qū)域。 在鏈路沖突圖中，處于極大團中的點表示全都互相沖突的鏈路。在上圖左所描述的網(wǎng)絡(luò)拓撲圖中，假設(shè)節(jié)點的傳輸半徑和干擾半徑相同，那么節(jié)點1和節(jié)點2進行數(shù)據(jù)傳輸，則節(jié)點2和節(jié)點3，節(jié)點2和節(jié)點6，節(jié)點3和節(jié)點4之間如果進行數(shù)據(jù)傳輸都會受到干擾。鏈路之間是否相互干擾主要通過前面所述的協(xié)議模型進行判定，例如鏈路兩頭的任何一個節(jié)點如果在其他鏈路節(jié)點集合的干擾范圍內(nèi)，這兩條鏈路就是相互干擾的，那么這兩個鏈路在沖突圖中就會有邊相連，表示它們?nèi)敉瑫r進行通信會互相沖突。 分布式信道分配方案沖突圖(conflict graph)的概念是很直觀的。很顯然，這種分配方式如果需要獲得統(tǒng)一的信道分配方案，需要指明鄰域的組劃分方法，因為組劃分方法的不同會直接導致分配方案的不同。 組劃分信道分配方案我們可以將信道分配分成如下兩個階段進行：鄰居節(jié)點和網(wǎng)絡(luò)接口卡的綁定，信道和網(wǎng)絡(luò)接口卡的綁定。信道分配問題，最簡單的方法就是給每個節(jié)點的網(wǎng)絡(luò)接口卡分配相同的信道集合，例如接口卡1分配1號信道，接口卡2分配2號信道，以此類推。在多信道無線Mesh網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)中存在多個可用信道，如何進行合理的資源分配，讓資源得到最佳的利用可以統(tǒng)一抽象為信道分配問題，該問題也是MAC協(xié)議設(shè)計的重點和難點所在。圖 SSCH信道跳變圖 多信道無線Mesh網(wǎng)絡(luò)中的信道分配多信道MAC協(xié)議設(shè)計是無線Mesh網(wǎng)絡(luò)中的關(guān)鍵技術(shù)之一．如何更準確、更快的傳輸路由信息，更好地保證網(wǎng)絡(luò)的連通性，是衡量MAC協(xié)議優(yōu)劣的重要指標。SSCH協(xié)議的另一個重要特性是同步跳變，當結(jié)點A準備向結(jié)點B發(fā)送大量數(shù)據(jù)時，結(jié)點A將某個虛擬信道的信道跳變圖案匹配到結(jié)點B的相應(yīng)虛擬信道的信道跳變圖案上，也即，結(jié)點A和B在某個虛擬信道上使用相同的信道跳變圖案，這樣，結(jié)點A和B就能一直在該虛擬信道上進行通信。SSCH協(xié)議的另一個重要特性是同步跳變，當結(jié)點A準備向結(jié)點B發(fā)送大量數(shù)據(jù)時，結(jié)點A將某個虛擬信道的信道跳變圖案匹配到結(jié)點B的相應(yīng)虛擬信道的信道跳變圖案上，也即，結(jié)點A和B在某個虛擬信道上使用相同的信道跳變圖案，這樣，結(jié)點A和B就能一直在該虛擬信道上進行通信。相鄰兩個結(jié)點可以在相同信道時隙通信或交換狀態(tài)信息，保證了網(wǎng)絡(luò)的連通性。2. 兩個結(jié)點有相同的，但不同，那么這兩個結(jié)點僅在奇偶時隙使用相同的信道。3個可用信道時，兩個結(jié)點可能的信道跳變圖案。邏輯分割（logical partition）是指在通信范圍內(nèi)的兩個結(jié)點不存在信道重疊的時隙而不能夠通信。在SSCH中，時間軸被劃分成時隙，連續(xù)多個時隙組成一幀，所有幀的第i個時隙形成第i個虛擬信道。2)每個時隙的開始，將當前的信道跳變圖案廣播給鄰居結(jié)點。 SSCH協(xié)議SSCH是一個基于時隙的分布式單接口多信道協(xié)議，工作在鏈路層，負責協(xié)調(diào)各結(jié)點的信道切換，不需要專門的控制信道，實現(xiàn)[6]。如果有多個這樣的信道，就任意選擇一個。如果有多個這樣的信道，就任意選擇一個。2)否則，如果發(fā)送結(jié)點的PCL中有高優(yōu)先級的信道，則選擇此信道。MMAC的信道分配算法是要選擇業(yè)務(wù)負載小的信道，目的是盡可能地平衡信道負載，減小競爭和退避所浪費的帶寬。如果分組中指定的信道處于高優(yōu)先級，則不改變狀態(tài)。如果發(fā)送結(jié)點和接收結(jié)點協(xié)商好某個信道，那么，這兩個結(jié)點就將該信道置為高優(yōu)先級狀態(tài)。低優(yōu)先級表示此信道至少已經(jīng)被一個鄰居結(jié)點所選用。每個信標間隔內(nèi)，一個結(jié)點最多只能有一個信道處于高優(yōu)先級狀態(tài)。另外，MMAC可以在ATIM窗口期間廣播消息，支持本地廣播功能。根據(jù)ATIMACK和ATIMRES分組，結(jié)點A和結(jié)點B的鄰居也就知道了結(jié)點A和結(jié)點B將使用信道1通信，并更新自己的PCL，以便于將來根據(jù)這些信息為自己選擇信道。在發(fā)送端和接收端通信范圍內(nèi)，被較少結(jié)點使用的信道將被優(yōu)先選取[4]。當一個新的信標間隔開始，所有節(jié)點都切換到信道1，進去到ATIM窗口，A等待一個隨機時延（避免沖突）后向B發(fā)送ATIM分組，ATIM分組中包含了A的PCL（Preferable Channel List），這個表中記錄了結(jié)點鄰域內(nèi)信道的使用情況。在這個場景整合，4個節(jié)點構(gòu)成鏈狀拓撲，按照ABCD順序排列。，時間軸被劃分為信標間隔（Beacon Interval），在每一個信標間隔的開始，有一個稱之為“ATIM(Ad Hoc Traffic Indication Message)Window”的時間窗口，該時間窗口的起始時刻，網(wǎng)絡(luò)中的所有節(jié)點都被強制切換到相同的信道上。 DCA的通信過程 MMAC協(xié)議MMAC（Multichannel MAC）主要是為了配置了一個網(wǎng)絡(luò)接口的節(jié)點而設(shè)計。最后，數(shù)據(jù)分組將在選擇的數(shù)據(jù)信道上發(fā)送。同樣，B用CTS控制它的鄰節(jié)點使用此信道。B收到RTS后，將RTS與它自己的CUL對比，找到一個可用的數(shù)據(jù)信道，然后回復(fù)CTS。每個節(jié)點分布式地保存CUL表，實時更新。表中的每個條目CUL[i]保存著鄰居節(jié)點什么時候使用信道的信息。每個節(jié)點維護兩個數(shù)據(jù)結(jié)構(gòu)：CUL和FCL?？刂菩诺烙脕斫鉀Q數(shù)據(jù)信道上的沖突和每個節(jié)點分配數(shù)據(jù)信道的問題：數(shù)據(jù)信道用來傳輸數(shù)據(jù)分組和確認分組。 .1 DCA協(xié)議動態(tài)信道分配（DCA，Dynamic Channel Assignment）是具有專用的控制信道、2個網(wǎng)絡(luò)接口的多信道MAC協(xié)議[4]。③ 無線Mesh簡化了網(wǎng)絡(luò)的維護與升級，每個節(jié)點都可以有多條可選路由，因而局部地區(qū)的升級與擴容將不會影響到整個網(wǎng)絡(luò)的運行，方便了網(wǎng)絡(luò)的維護。多跳還可以充分實現(xiàn)頻率再用，提高頻譜利用率，借此提高網(wǎng)絡(luò)的容量。⑥ 移動性方面，Adhoc網(wǎng)絡(luò)用戶節(jié)點實現(xiàn)用戶功能，網(wǎng)絡(luò)和互聯(lián)都依賴于中的終端節(jié)點的一大，增加了路由和配置實現(xiàn)的難度。用戶可以以不同的電臺接入，有效改善了網(wǎng)絡(luò)的流量。另外也降低了對用戶節(jié)點的功能要求和價格[3]。另外，無線Mesh網(wǎng)絡(luò)和Adhoc網(wǎng)絡(luò)在功率控制和移動性要求方面也略有不同。無線Mesh網(wǎng)絡(luò)還能與現(xiàn)有的各種網(wǎng)絡(luò)兼容，如前面所述，這樣，一個網(wǎng)絡(luò)中的用戶通過無線分層結(jié)構(gòu)可以獲得其他網(wǎng)絡(luò)的服務(wù)，這是一個很有前景的應(yīng)用。② 無線Mesh網(wǎng)絡(luò)支持與Mesh路由器網(wǎng)絡(luò)使用相同射頻技術(shù)的傳統(tǒng)節(jié)點。2 與Adhoc網(wǎng)絡(luò)的不同之處① 無線Mesh路由器通過無線連接組成網(wǎng)絡(luò)骨干，實現(xiàn)大范圍的覆蓋和連接。無線Mesh也具有Adhoc網(wǎng)絡(luò)結(jié)構(gòu)靈活、易于部署和配置、容錯以及網(wǎng)狀連接多點到多點通信的那個特點，使得無線Mesh網(wǎng)絡(luò)的初始部署成本低，并且可以根據(jù)需要來逐步擴容。為了能夠?qū)崿F(xiàn)這個目標，無可避免的采用了多跳Mesh網(wǎng)絡(luò)。1 具有Adhoc網(wǎng)