3.對于算法的節點插入和移除的兩個過程

　　對于一個被給定的藍牙WPAN拓撲，討論兩種分布式過程來處理拓撲變化。第一個過程是允許在WPAN中插入一個新的節點;第二個過程是從網絡中去除一個節點，這兩個過程要達到的主要目標是滿足藍牙規范的限制條件，即全網絡連通性，有高的吞吐流量，降低控制信息的開銷等。當然，可以加入一個新節點到網絡中去，也意味著可以同時加入幾個節點。因此，根據這個，我們可以依靠最初給定的一系列藍牙設備用來建立一個可增長的BT--WPAN或者形成一個網絡拓撲。

　　（1）插入節點過程

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

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

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

　　2位：節點的流量的等級；

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

　　設a是開始查詢過程的節點，正如上所述，根據收到的鄰近的節點的回應，a它將決定對哪個節點進行尋呼，回應的節點要么是屬于孤立的徽微網要么不屬于孤立的微微網。除此之外，它還具有以下可能：

　　具有少于7個從節點的主節點；

　　從節點；

　　即是從節點又是橋節點；

　　即是主節點又是橋節點；

　　已經具有7個節點的主節點；

　　像a一樣也在等著加入到藍牙WPAN中。

　　a根據以下的優先順序來選擇加入到哪個回應節點；

　　1）屬于孤立的微微網主節點（或者既是主節點又是橋節點的網絡節點）

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

　　如果a收到一個不屬于孤立微微網的節點的回應，它將按如下的方式選擇：

　　1）如果回復的是從節點少于7個的主節點（或者既是主節點又是橋節點），則a加入此節點并且創建一個新的微微網。通過主從節點的角色互換，a變成孤立的微微網中的從節點（或者是橋節點）

　　2）如果回復的節點是從節點（或者既是從節點又是橋節點）或者是具有7個從節點的主節點（或者既是主節點又是橋節點），則“創建一個新的含有該節點的微微網。

　　2）屬于孤立的微微網從節點（或者既是從節點又是橋節點的網絡節點）

　　有兩種不同的情況：

　　1）沒有連接到散射網的其它節點回復了a的查詢，在這種情況下，a將有以下的情形：

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

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

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

　　3、不屬于孤立的微微網但是又少于7個從節點的主節點

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

　　不屬于孤立的微微網從節點

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

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

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

　　5、不屬于孤立的微微網的既是從節點又是橋節點的網絡節點

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

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

　　2）a想成為從節點。在這個新的微微網中，a作為從節點，被選擇的節點作為主節點而且還充當該微微網與它先前所在的微微網的橋節點。

　　6、不屬于孤立的微微網的既是主節點又是橋節點的網絡節點

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

　　7、不屬于孤立的微微網并且已有7個從節點的主節點

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

　　1）在這個新的微微網中，a仍然是主節點，而被選擇的節點既是從節點又是橋節點;

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

　　8、新節點

　　節點a尋呼到一個新節點，這樣創建一個以a為主節點的微微網。然后，如果兩個節點協商后，可以互換角色。在該微微網中，同樣可以包含一些回應了節點查詢的其它節點。然而，為了保持藍牙WPAN拓撲的連接性，要么是a要么是它微微網中的其它一些節點必須尋呼現有藍牙WPAN中節點。

　　移去節點的過程

　　節點離開網絡引起的變化主要取決于該節點在藍牙WPAN中作用，有下面四種情況：

　　。該節點是從節點：該情況最簡單，那就是該節點僅僅是從網絡中移去，而沒有改變拓撲的任何結構。

　　。該節點是主節點：在該微微網中的從節點將在藍牙WPAN中尋找一個新的節點來重新建立連接，因此，每一個從節點都要執行插入程序，而橋節點仍然作為橋節點保持與其它微微網的連接。

　　。該節點既是主節點又是橋節點：這種情況的處理方式與第二種情況的處理方式一樣。

　　。該節點既是從節點又是橋節點：如果有其它節點可以取代該節點，那么它就可從網絡中很簡單的移去。否則的話，就必須尋找一個可以替代該節點的節點這樣，在此微微網中主節點將執行查詢程序，如果不能找到通向目標微微網的橋節點，它將命令它的從節點執行查詢程序以尋找橋節點。如果在藍牙WPAN范圍中，在這些節點所能傳輸的的范圍內沒有找到這樣的節點，那么該微微網就與藍牙WPAN斷開。

　　2.射網的重要性能分析

　　3藍牙組網的仿真結果和分析

　　小結

　　本章介紹了藍牙個人區域網絡的基本知識，明確了藍牙微微網和散射網的概念，分析了藍牙散射網的網路特點，闡述了藍牙散射網拓撲構建的重要性以及藍牙散射網拓撲構建算法需要解決的關鍵問題和衡量藍牙散射網拓撲構建算法的標準。藍牙自組個人區域網絡的主從特性、動態性、跳頻特性雖然使藍牙組網更加靈活，但這些特點以及藍牙節點本身多為個人數字設備，節點運行的協議和應用程序必須考慮節點處理能力、內存和能耗等條件，都無疑增加了網絡拓撲構建 算法、網絡路由等算法的難度。

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

　　本章從介紹藍牙節點的工作狀態和藍牙物理鏈路的建立過程入手，提出一種備份式的藍牙散射網拓撲構建算法。算法吸收了Bluestars算法中以節點的可用資源為標準的方法，來選取主節點，初始主節點建立第一個微微網后，主節點選取最多3個橋節點和3個次主節點，通過逐級展開的方法建立相互連接的微微網，最終形成連通的藍牙散射網，散射網形成后通過節點備份的方法，提高網絡的自愈能力。本章最后運用數學推導的方法證明了算法幾項重要的性能指標為：時間復雜度為O（logN）、消息復雜度為O（N）、網絡直徑為O（logN）、具有較少的微微網個數和節點角色的平均數。