3.對于算法的節(jié)點(diǎn)插入和移除的兩個過程

　　對于一個被給定的藍(lán)牙WPAN拓?fù)?，討論兩種分布式過程來處理拓?fù)渥兓５谝粋€過程是允許在WPAN中插入一個新的節(jié)點(diǎn);第二個過程是從網(wǎng)絡(luò)中去除一個節(jié)點(diǎn)，這兩個過程要達(dá)到的主要目標(biāo)是滿足藍(lán)牙規(guī)范的限制條件，即全網(wǎng)絡(luò)連通性，有高的吞吐流量，降低控制信息的開銷等。當(dāng)然，可以加入一個新節(jié)點(diǎn)到網(wǎng)絡(luò)中去，也意味著可以同時加入幾個節(jié)點(diǎn)。因此，根據(jù)這個，我們可以依靠最初給定的一系列藍(lán)牙設(shè)備用來建立一個可增長的BT--WPAN或者形成一個網(wǎng)絡(luò)拓?fù)洹?/p>

　?。?）插入節(jié)點(diǎn)過程

　　一個節(jié)點(diǎn)想快速加入到WPAN中來，它必須首先發(fā)送一個普通的查詢信息來懇求它附近的節(jié)點(diǎn)是否可以加入。相反，如果一個節(jié)點(diǎn)的目的是加入到一個網(wǎng)絡(luò)中并有良好連接，即想加入到具有低流量的微微網(wǎng)中或者扮演一個特殊的角色，它就必須使用專用的查詢。

　　下面部分，討論承載查詢回復(fù)的FHS包。注意到，一個數(shù)據(jù)包FHS它包含有設(shè)備類型的標(biāo)記，加上5比特就能夠用于傳遞未來的信息。這其中2位比特預(yù)留下來以備將來使用，AM-ADDR領(lǐng)域的3位在查詢回應(yīng)中不使用。我們定義這5位傳送以下信息：

　　2位：電池的電量等級（如：低于25%，在25%和50%之間，在50%到75%之間，高于75%）；

　　2位：節(jié)點(diǎn)的流量的等級；

　　1位：這個節(jié)點(diǎn)是否屬于孤立微微網(wǎng)。如果一個微微網(wǎng)沒有于任何一個微微網(wǎng)連接或者它附近的微微網(wǎng)都只僅僅與它相連那我們就稱之為孤立的微微網(wǎng)。如果該節(jié)點(diǎn)屬于孤立的微微網(wǎng)，那么該位置1，否則置0。

　　設(shè)a是開始查詢過程的節(jié)點(diǎn)，正如上所述，根據(jù)收到的鄰近的節(jié)點(diǎn)的回應(yīng)，a它將決定對哪個節(jié)點(diǎn)進(jìn)行尋呼，回應(yīng)的節(jié)點(diǎn)要么是屬于孤立的徽微網(wǎng)要么不屬于孤立的微微網(wǎng)。除此之外，它還具有以下可能：

　　具有少于7個從節(jié)點(diǎn)的主節(jié)點(diǎn)；

　　從節(jié)點(diǎn)；

　　即是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)；

　　即是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)；

　　已經(jīng)具有7個節(jié)點(diǎn)的主節(jié)點(diǎn)；

　　像a一樣也在等著加入到藍(lán)牙WPAN中。

　　a根據(jù)以下的優(yōu)先順序來選擇加入到哪個回應(yīng)節(jié)點(diǎn)；

　　1）屬于孤立的微微網(wǎng)主節(jié)點(diǎn)（或者既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)）

　　如果a收到不止一個屬于孤立微微網(wǎng)的主節(jié)點(diǎn)的回應(yīng)，它將選擇從節(jié)點(diǎn)少于7個和低流量的的主節(jié)點(diǎn)加入。如果不止一個主節(jié)點(diǎn)滿足上述條件，那么它還根據(jù)該節(jié)點(diǎn)的電池電量的等級來考慮。注意到a節(jié)點(diǎn)根據(jù)相關(guān)的RSSI估計(jì)每個回應(yīng)節(jié)點(diǎn)的距離。把被選擇的主節(jié)點(diǎn)記為u，節(jié)點(diǎn)a尋呼u并創(chuàng)建一個新的微微網(wǎng)，此時“a是主節(jié)點(diǎn)，u是從節(jié)點(diǎn)，過一會兒，這兩個節(jié)點(diǎn)的角色進(jìn)行互換，這樣，在微微網(wǎng)中，a就變成從節(jié)點(diǎn)，并且受主節(jié)點(diǎn)u的支配。

　　如果a收到一個不屬于孤立微微網(wǎng)的節(jié)點(diǎn)的回應(yīng)，它將按如下的方式選擇：

　　1）如果回復(fù)的是從節(jié)點(diǎn)少于7個的主節(jié)點(diǎn)（或者既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)），則a加入此節(jié)點(diǎn)并且創(chuàng)建一個新的微微網(wǎng)。通過主從節(jié)點(diǎn)的角色互換，a變成孤立的微微網(wǎng)中的從節(jié)點(diǎn)（或者是橋節(jié)點(diǎn)）

　　2）如果回復(fù)的節(jié)點(diǎn)是從節(jié)點(diǎn)（或者既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)）或者是具有7個從節(jié)點(diǎn)的主節(jié)點(diǎn)（或者既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)），則“創(chuàng)建一個新的含有該節(jié)點(diǎn)的微微網(wǎng)。

　　2）屬于孤立的微微網(wǎng)從節(jié)點(diǎn)（或者既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)）

　　有兩種不同的情況：

　　1）沒有連接到散射網(wǎng)的其它節(jié)點(diǎn)回復(fù)了a的查詢，在這種情況下，a將有以下的情形：

　?。?）a具有可以成為主節(jié)點(diǎn)的足夠的處理能力和能t容盤，如果這樣，則a通過尋呼一個或多個對它的查詢做過響應(yīng)的從節(jié)點(diǎn)來創(chuàng)建一個新的微微網(wǎng)。那么這些從節(jié)點(diǎn)就成了剛形成的微微網(wǎng)和以前微微網(wǎng)之間的橋節(jié)點(diǎn)。對于這些被尋呼的從節(jié)點(diǎn)，a可以根據(jù)其節(jié)點(diǎn)的流量、電池狀態(tài)和空間的距離來選擇。假設(shè)一個微微網(wǎng)被一短比特位的字符來標(biāo)識，即小于5位的長度，并且在微徽網(wǎng)中的每一個節(jié)點(diǎn)都知道所在的微微網(wǎng)的標(biāo)識。一個被a尋呼的從節(jié)點(diǎn)可以在承載尋呼響應(yīng)的FHS包中利用這’5位來標(biāo)示這個信息。這樣，a隨時有可能中斷尋呼的過程，因?yàn)樗B接的節(jié)點(diǎn)屬于已經(jīng)有微徽網(wǎng)間連接的節(jié)點(diǎn)。

　?。?）a想成為從節(jié)點(diǎn)。a.根據(jù)流t，電池等級和空間距離來選擇可以加入的節(jié)點(diǎn)，它和被選擇的節(jié)點(diǎn)形成一個新的微微網(wǎng)，然后，在該微微網(wǎng)中，這兩個節(jié)點(diǎn)互換角色，這樣，。就變成了從節(jié)點(diǎn)，而被選擇的節(jié)點(diǎn)則變成了在新微微網(wǎng)和以前微微網(wǎng)之間的主節(jié)點(diǎn)和橋節(jié)點(diǎn)。

　　2）a收到一個不屬于孤立微微網(wǎng)的的節(jié)點(diǎn)的回復(fù)。在這種情況下，a試圖連接剩余部分散射網(wǎng)中的孤立節(jié)點(diǎn)，并且按照以下優(yōu)先次序在散射網(wǎng)中選擇要連接的節(jié)點(diǎn)：從節(jié)點(diǎn)、既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)的節(jié)點(diǎn)、主節(jié)點(diǎn)、既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)、具有7個從節(jié)點(diǎn)的主節(jié)點(diǎn)。如果有必要，將依照以下準(zhǔn)則進(jìn)一步進(jìn)行選擇：流量，電池等級，空間距離。然后，完成要選擇的節(jié)點(diǎn)后，a創(chuàng)建一個新的微微網(wǎng)。

　　3、不屬于孤立的微微網(wǎng)但是又少于7個從節(jié)點(diǎn)的主節(jié)點(diǎn)

　　在現(xiàn)有的可利用的主節(jié)點(diǎn)之中，。選擇具有最小流量的一個節(jié)點(diǎn)，如果在流量相同的情況下，然后考慮電池等級，其次是考慮該節(jié)點(diǎn)離a的空間距離。為了避免微微網(wǎng)之間的重盈和減少微微網(wǎng)內(nèi)部之間的干擾，離“較近的節(jié)點(diǎn)具有優(yōu)先權(quán)。把被選擇的主節(jié)點(diǎn)記為產(chǎn)，節(jié)點(diǎn)a加入聲創(chuàng)建一個新的微微網(wǎng)，此處a是主節(jié)點(diǎn)，尸是從節(jié)點(diǎn)，過一會兒，這兩個節(jié)點(diǎn)的角色互換，這樣，在微微網(wǎng)中，a變成從節(jié)點(diǎn)，并且受主節(jié)點(diǎn)產(chǎn)的支配。

　　不屬于孤立的微微網(wǎng)從節(jié)點(diǎn)

　　在2的1）中，介紹了它的兩種可能的情況：

　　1）“具有可以成為主節(jié)點(diǎn)的足夠的處理能力和能量，如果這樣，則a通過尋呼一個或多個響應(yīng)過它的查詢的節(jié)點(diǎn)來創(chuàng)建一個新的微微網(wǎng)，同時在新的微微網(wǎng)和以前的微微網(wǎng)中的節(jié)點(diǎn)就成為了橋節(jié)點(diǎn)。

　　2）a想成為從節(jié)點(diǎn)。在現(xiàn)有的可以利用的節(jié)點(diǎn)中選擇可以加入的節(jié)點(diǎn)，a和被選擇的節(jié)點(diǎn)形成一個新的微微網(wǎng)，然后，在該微微網(wǎng)中，這兩個節(jié)點(diǎn)互換角色，這樣，a就變成了從節(jié)點(diǎn)，而被選擇的節(jié)點(diǎn)變成了主節(jié)點(diǎn)和橋節(jié)點(diǎn)。

　　5、不屬于孤立的微微網(wǎng)的既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)

　　像前面所說的一樣，它也有兩種可能的情況：

　　l）。具有可以成為主節(jié)點(diǎn)的足夠的處理能力和能量，a依照以下三條準(zhǔn)則來選擇要尋呼的節(jié)點(diǎn)（該節(jié)點(diǎn)既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)）：流量;電池等級;空間距離。這樣一個新的微微網(wǎng)形成，此處。作為主節(jié)點(diǎn)而被選擇的節(jié)點(diǎn)作為從節(jié)點(diǎn)。

　　2）a想成為從節(jié)點(diǎn)。在這個新的微微網(wǎng)中，a作為從節(jié)點(diǎn)，被選擇的節(jié)點(diǎn)作為主節(jié)點(diǎn)而且還充當(dāng)該微微網(wǎng)與它先前所在的微微網(wǎng)的橋節(jié)點(diǎn)。

　　6、不屬于孤立的微微網(wǎng)的既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)

　　在現(xiàn)有的可利用的節(jié)點(diǎn)（既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)）之中，a依照以下三條準(zhǔn)則來選擇要加入的節(jié)點(diǎn)：流量：電池等級：空間距離。在a創(chuàng)建一個新的微微網(wǎng)之后，它與被選擇的節(jié)點(diǎn)互換一下角色，從而在微微網(wǎng)中a成為從節(jié)點(diǎn)并且被它所選擇的節(jié)點(diǎn)（既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)）所支配。

　　7、不屬于孤立的微微網(wǎng)并且已有7個從節(jié)點(diǎn)的主節(jié)點(diǎn)

　　在現(xiàn)有的可利用的節(jié)點(diǎn)之中，a選擇具有最小流量的一個節(jié)點(diǎn)，如果在流量相同的情況下，然后考慮電池等級，其次是考慮該節(jié)點(diǎn)離“的空間距離。以a為主節(jié)點(diǎn)的一個新的微微網(wǎng)被創(chuàng)建了。此時有兩種可能性：

　　1）在這個新的微微網(wǎng)中，a仍然是主節(jié)點(diǎn)，而被選擇的節(jié)點(diǎn)既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn);

　　2）這兩個節(jié)點(diǎn)互換角色，這樣，被選擇的主節(jié)點(diǎn)使得它的其中的一個從節(jié)點(diǎn)處于閑置狀態(tài)，該閑置節(jié)點(diǎn)可以運(yùn)行插入程序來尋找新的微微網(wǎng)以便加入。要不然，a則和在這個微微網(wǎng)中的其它節(jié)點(diǎn)輪流的處于閑置狀態(tài)。

　　8、新節(jié)點(diǎn)

　　節(jié)點(diǎn)a尋呼到一個新節(jié)點(diǎn)，這樣創(chuàng)建一個以a為主節(jié)點(diǎn)的微微網(wǎng)。然后，如果兩個節(jié)點(diǎn)協(xié)商后，可以互換角色。在該微微網(wǎng)中，同樣可以包含一些回應(yīng)了節(jié)點(diǎn)查詢的其它節(jié)點(diǎn)。然而，為了保持藍(lán)牙WPAN拓?fù)涞倪B接性，要么是a要么是它微微網(wǎng)中的其它一些節(jié)點(diǎn)必須尋呼現(xiàn)有藍(lán)牙WPAN中節(jié)點(diǎn)。

　　移去節(jié)點(diǎn)的過程

　　節(jié)點(diǎn)離開網(wǎng)絡(luò)引起的變化主要取決于該節(jié)點(diǎn)在藍(lán)牙WPAN中作用，有下面四種情況：

　　。該節(jié)點(diǎn)是從節(jié)點(diǎn)：該情況最簡單，那就是該節(jié)點(diǎn)僅僅是從網(wǎng)絡(luò)中移去，而沒有改變拓?fù)涞娜魏谓Y(jié)構(gòu)。

　　。該節(jié)點(diǎn)是主節(jié)點(diǎn)：在該微微網(wǎng)中的從節(jié)點(diǎn)將在藍(lán)牙WPAN中尋找一個新的節(jié)點(diǎn)來重新建立連接，因此，每一個從節(jié)點(diǎn)都要執(zhí)行插入程序，而橋節(jié)點(diǎn)仍然作為橋節(jié)點(diǎn)保持與其它微微網(wǎng)的連接。

　　。該節(jié)點(diǎn)既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)：這種情況的處理方式與第二種情況的處理方式一樣。

　　。該節(jié)點(diǎn)既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)：如果有其它節(jié)點(diǎn)可以取代該節(jié)點(diǎn)，那么它就可從網(wǎng)絡(luò)中很簡單的移去。否則的話，就必須尋找一個可以替代該節(jié)點(diǎn)的節(jié)點(diǎn)這樣，在此微微網(wǎng)中主節(jié)點(diǎn)將執(zhí)行查詢程序，如果不能找到通向目標(biāo)微微網(wǎng)的橋節(jié)點(diǎn)，它將命令它的從節(jié)點(diǎn)執(zhí)行查詢程序以尋找橋節(jié)點(diǎn)。如果在藍(lán)牙WPAN范圍中，在這些節(jié)點(diǎn)所能傳輸?shù)牡姆秶鷥?nèi)沒有找到這樣的節(jié)點(diǎn)，那么該微微網(wǎng)就與藍(lán)牙WPAN斷開。

　　2.射網(wǎng)的重要性能分析

　　3藍(lán)牙組網(wǎng)的仿真結(jié)果和分析

　　小結(jié)

　　本章介紹了藍(lán)牙個人區(qū)域網(wǎng)絡(luò)的基本知識，明確了藍(lán)牙微微網(wǎng)和散射網(wǎng)的概念，分析了藍(lán)牙散射網(wǎng)的網(wǎng)路特點(diǎn)，闡述了藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建的重要性以及藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建算法需要解決的關(guān)鍵問題和衡量藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建算法的標(biāo)準(zhǔn)。藍(lán)牙自組個人區(qū)域網(wǎng)絡(luò)的主從特性、動態(tài)性、跳頻特性雖然使藍(lán)牙組網(wǎng)更加靈活，但這些特點(diǎn)以及藍(lán)牙節(jié)點(diǎn)本身多為個人數(shù)字設(shè)備，節(jié)點(diǎn)運(yùn)行的協(xié)議和應(yīng)用程序必須考慮節(jié)點(diǎn)處理能力、內(nèi)存和能耗等條件，都無疑增加了網(wǎng)絡(luò)拓?fù)錁?gòu)建 算法、網(wǎng)絡(luò)路由等算法的難度。

　　目前藍(lán)牙規(guī)范中對微微網(wǎng)內(nèi)的通信協(xié)議有了明確的規(guī)定，但對藍(lán)牙散射網(wǎng)的研究，還處于探索階段，是各國科學(xué)家感興趣和重點(diǎn)研究的課題之一，越來越多的研究成果完善了藍(lán)牙網(wǎng)絡(luò)的應(yīng)用，提高了藍(lán)牙產(chǎn)品的普及率。中國是人口密集，商業(yè)經(jīng)濟(jì)活動集中、人均收入還比較低的國家和地區(qū)，低成本、組網(wǎng)簡單靈活的藍(lán)牙產(chǎn)品將會有更廣闊的應(yīng)用前景。它的應(yīng)用將遍及很多領(lǐng)域，如移動通信、計(jì)算機(jī)及周邊設(shè)備、個人隨身信息和娛樂設(shè)備、網(wǎng)絡(luò)接入設(shè)備、醫(yī)療保健、金融、軍事等。它是面對個人的近距離無線技術(shù)，是人與機(jī)器之間交流的好助手。

　　本章從介紹藍(lán)牙節(jié)點(diǎn)的工作狀態(tài)和藍(lán)牙物理鏈路的建立過程入手，提出一種備份式的藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建算法。算法吸收了Bluestars算法中以節(jié)點(diǎn)的可用資源為標(biāo)準(zhǔn)的方法，來選取主節(jié)點(diǎn)，初始主節(jié)點(diǎn)建立第一個微微網(wǎng)后，主節(jié)點(diǎn)選取最多3個橋節(jié)點(diǎn)和3個次主節(jié)點(diǎn)，通過逐級展開的方法建立相互連接的微微網(wǎng)，最終形成連通的藍(lán)牙散射網(wǎng)，散射網(wǎng)形成后通過節(jié)點(diǎn)備份的方法，提高網(wǎng)絡(luò)的自愈能力。本章最后運(yùn)用數(shù)學(xué)推導(dǎo)的方法證明了算法幾項(xiàng)重要的性能指標(biāo)為：時間復(fù)雜度為O（logN）、消息復(fù)雜度為O（N）、網(wǎng)絡(luò)直徑為O（logN）、具有較少的微微網(wǎng)個數(shù)和節(jié)點(diǎn)角色的平均數(shù)。