介紹演講的主題是無線電的省電功能。
各位同學，今天要講的主題title很長，所以我就不唸了，不過關鍵在hybrid，所以我會把一些整合的現有的系統作一個呈現，那這些keyword以下都會在我們投影片裡看到，那就請大家看一下。本來那個演講一開始都要講一些笑話，那我不太會講笑話，所以我就用動畫來代替。這裡有一中國的諺語是"人休息是為了走更遠的路"，把他翻成英文就是這樣。這裡有個動畫，那這有兩個娃娃阿，那這兩個娃娃他們平常是感情很好，他們一定要隨時能互相聯繫，那這兩個娃娃是用電池來驅動，他們為了能夠...因為他個兩個娃娃能量有限，他們為了能夠省更多的能量阿，所以他們經常在不需要講話的時候進入休眠模式，也就是睡覺模式；結果他們有個需求就是隨時又要能夠互相聯絡一下，所以就講好了，在同一個時間睡覺，然後固定時間到了，又一起醒來，然後互相大家對話幾句，然後又很放心的繼續睡覺，好，那目的是休息是為了走更長遠的話，那這個是第一個動畫。那我們再看一個動畫，這裡又有兩個娃娃，他們感情一樣很好，所以呢，他們也要要隨時能夠聊上幾句，那同樣的他們也是要休息是為了走更長遠的路，那一樣，他們經常進入所謂的休眠模式，然後在定期的時候又醒來，他們又同時要講上幾句話，聯繫一下。那你可以看到上面的動畫和下面的動畫他們不一樣的是，上面他們的睡跟省是同步的，睡三分鐘比如醒來60秒，然後又睡三分鐘醒來60秒。那底下這個是睡醒是不同步的，所以比如說我醒來，剛好你也醒來，那我們就能講上幾句話，那常常碰到一個狀況就是左邊的娃娃醒來的時候右邊的娃娃正好睡著了，那或是相反地，只要是這種狀況喔，一個娃娃醒來而另外一個娃娃沒醒的話，他們就對不上話，所以久了以後感情就疏離了，不能像以前感情很好的狀況，那這個就是今天我演講要講的東西。一樣的，在今天的通訊設備能夠在省電的情況之下，能夠保證他們在定期的時間內能夠用無線電聯絡的上，那你就能了解為甚麼這個問題。那當然無線電設備最省電的情況就是要能夠一起睡一起醒，比如說一起把無線電打開，一起把無線電關掉，那有幾個狀況就是無線電的時間跟訊號沒辦法百分之百同步，那這個時候你要用以下這兩個狀況來討論，那這個會比較省電，那這個會比較不省電，但是他有個特性就是會比較時機一點，所以我們以下介紹的方法就是會結合以上同步的方式跟不同步的方式，也就是這個hybrid的方式，問題是我們大家把，現在無線電最流行的wireless的local gateway network的標準802.11拿來當作我們研究的基礎，我們講一下什麼是802.11所串成的limits，或是我們未來的隨意網，802.11的隨意網，然後再講為甚麼要討論讓你的設備用的更久，休息是為了走更遠的路，然後我們要怎樣把兩個不同類型的電腦，同步的跟非同步的把他合在一起，然後講一下一些母體結構的東西。
說明使用 802.11的一些好處，以及價格與產能的相關性
首先介紹 802.11 的隨意網路，那 802.11 很有名喔，在座的很多同學拿 notebook ，上面應該都有 802.11 的網路卡，那在 1997 年 IEEE 就批准世界標準，那在 1999 年又有一個 session 出來，我們知道從商業上來看，這裡有一個價格的預測，還有出貨量的預測，還有我們看看他的出貨量在我們現在所在的 2006 年大概有 50 個 million ，在他的價格上下降到了 100 美元，或 5,60 美元，這其實就是一個經濟規模的曲線，他告訴我們這個東西已經變成我們日常生活中一個經濟產能，出貨量會持續的上升，價格可能會持續的下降，當然這裡會有一條穩定的線，這裡會有一個趨近的線而這裡也會有一個趨近的線，這裡價格會相當低，那他的數量仍然會持續的增加到一定的數量，這個是他的 family ，這個不是我們今天的主題喔，所以這邊讓大家看一下就好，這裡有大家所熟悉的 802.11b ， 802.11g ，還有 802.11a ，還有現在 802.11 super g ，速度可以達到 108Mb/s ，這是告訴我們 802.11 的 family 非常多個 working group ，在使的通訊協定更加順暢，這裡列的只是一部分，包括作 security ，包括作 QoS ，包括作這個 (...) 等等，都要有非常好的 support ，所以用這個 802.11 絕對不用擔心會有未來都不會出現不會繼續進步的狀況。
802.11有兩種模式：Infrastructure mode & Ad Hoc mode，與multihop Ad Hoc network的簡單原理和應用領域
那 802.11 有兩種模式，一個模式叫 Infrastructure mode ，一個叫做 Ad Hoc mode ，基本上使用者在使用筆記型電腦的時候作資料存取，都會有基礎建設， AP 就是你的基礎建設，有些 AP 是透過一些後面的有線網路作連線，資料存取的到你的 AP ，那基本上你就不會注意到，這就是所謂的 Infrastructure mode 。那麼用過無線電網路卡就會知道那裡還有一個 mode 叫 Ad Hoc mode ，也是隨易模式，他就是以下這個圖示，就是沒有基地台，就叫做 Ad Hoc mode 。那 Ad Hoc mode 就是不需要基地台，那你的筆記型電腦或 PDA 的網路卡可以作互通，就叫做 Ad Hoc mode 。那 802.11 的 Ad Hoc mode 他是定義在所謂的 one hop 環境，就是所謂的單跳模式，就是說我們彼此在對方的無線電的通訊範圍之內的時候，是可以這個 .... 彼此在互相的無線電的傳輸範圍內可以連線，就叫 one hop Ad Hoc mode 。那你剛剛看到的動畫裡面，出現了一個狀況就是，剛剛這裡有一個 PDA ，他往左邊移的時候呢，那會造成一個新的連線，他會感應到在我的左側其他的，也是開在 Ad Hoc mode 的電腦出現，那就會有一個新的連線出現，那你看到這裡有什麼變化？那其實因為這個新的連線，所以我這裡的 A 電腦會透過 one hop ， two hop ， three hop 與這邊的 E 電腦連線上，所以這就是一個 three hop 的一個 path ，所以當你在使用你的 Ad Hoc 模式，在你的電腦上作無線電傳輸的時候，那你其實所採用的就是所謂 multihop Ad Hoc network 。那這個 one hop 的 Ad Hoc network 比較簡單，大家都在彼此的附近範圍傳輸，也有類似 central control 的味道，一個封包一送所有的人都收到，這個是比較簡單的狀況。那我們會討論比較複雜的狀況就是，假如你的網路是經過多跳的，能夠互相通訊的情況之下，那其實是通常的多，那當然它也是廣泛的多，應用的廣泛，所以我們今天要討論的是 multihop Ad Hoc network 這樣子的模式。那這樣的模式在國際上的研究其實已經十多年了，那最早是 IEEE 的 Internet Society IETF Task Force ， Internet Engineering Task Force 網際網路工程跟編組裡面有一個小組 MARS ，就是 Manage on SMAR ，那 manage 就是 no Ad Hoc network 這樣的縮寫，那這個討論的就是我們剛剛講的， of wireless normal host mobile on temporary ，一個臨時構成的網路，比如說 A of ?? is the infrastructure ，沒有臨時擴充網路的這樣的一個環境，而且希望不要有任何的藉助， centralized 網路的環境。那其實有這樣的需求了，大概就是我們看看，那最有需求的就是軍方，就在戰場上的時候，戰場上很難得會有基礎建設，所以大家很快的把 notebook 打開，或是把 PDA 打開，就可以串成網路；或者 disaster rescue ，那如災難現場阿， 921 地震以後全台斷電，那基地台都失效了，那怎麼辦？還能有網路嗎，可以阿， Ad hoc mode 一切阿，大家都往那邊串上，所以那個在急救災難現場，是可以用的。跟某個同學在外面不期而遇，那實際上我們都沒有網路的傳輸，如果我們有 Ad Hoc 模式的話，我們可以打開電腦就做通訊。那為了 outdoor activity ，假如我們今天不在這演講而是到戶外去演講，那到後山去演講，那邊或許假如假設沒有基地台的話，那我們還是希望互相能夠存取資料的話，那我們可以透過 Ad Hoc network 來達成，所以 Ad Hoc network 沒有基地台，所以就有不同的應用，就是 Applications 。
802.11在不同的layer有不同的省電研究方向
所以我們剛剛所講的網路裡面，一個 Single hop ，那有 Multihop 的， Single hop 是我們剛剛講過它是不會 connected?? ，所有的人都在彼此的傳輸範圍裏面，那 Multihop 呢，就是節點式透過另外一個，ㄜ ... 透過 shared of intermediate node 跟另外一個節點作通訊，那這個 Multihop network 其實複雜多了，他會構成一些有效的 partition 的問題：網路分成兩半阿，彼此都不 ˋ 知道對方存在，然後還有一個網路冗何的問題，怎樣把分成兩半的網路再合接，這個比較會討論一下。所以我們今天的主題是 Multihop 的 Ad Hoc network 。所以我們來看，這樣的網路上面，我們為什麼挑這個網路的問題來討論？那因為在這些 total 的 device ，我們一一的講，就是可攜式的，可攜式電腦，那都是靠電池來驅動的，透過這樣的電力來源，那我們知道電池的技術進步的相當緩慢，我們 IC 有所謂的莫爾定律，或者有後莫爾定律，每一八個月， IC 的密度就會增加一倍，讓我們的運作速率也變快，那電池沒有這樣一個技術的進步在那，所以電池其實嚴重落後我們其他的技術的發展，所以我們如何省電變成一個關鍵的問題，，所有的 device 都是由 battery 來 support ，這就是我們為什麼要挑這個問題來研究，可以的話可以幫我們學校省電，那在這個 802.11 上面呢， power saving problems ，或者 solution to power saving problems ，從三個方向去討論。第一個方向在 physical layer 討論，那控制傳輸範圍從硬體上去控制無線電的傳輸範圍，那第二個層次是在 MAC layer 做討論，就是在媒體存取控制層，那這個地方講的就是，在我可以有時候把無線電關掉而省電，那你要會看一個統計圖表，統計表單，就是無線電網路卡關掉無線電模式之後他的耗電量是原來的二十分之一，所以我可以省掉二十分之十九的電，所以我們就討論一下在 MAC layer 下我們可以做一些省電的管理，還有一些相關的研究，那在另外還有一些是在 network layer 所做的研究，就是我怎樣能夠在遶徑的時候，能夠考慮省電的因素，這裡也有一些相關的研究，我就列了一些，而且在近期 2004,2005,2006 還是有很多研究在這邊做探討。
Physical layer 的省電例子：縮小通訊範圍，增加空間的利效率
那我們現在稍微把 physical layer 所做的事情稍微討論一下，那這個 ... 這裡有三個六對無線電的傳輸設備 A,B,C ， A 正在送資料給 B ，那 D 正好要送資料給 C ，恩 ..C 正好要送資料給 D ， D 正好要送資料給 F ，所以在這個情況之下，我們要問一個狀況，假如 A 正在送資料給 B 的情況下，那我們要問， C 可以同時送給 D 嗎？那 D 可以同時送給 F 嗎？那我們的答案是不可以的，因為無線電的干擾，基本上是在資料發送源固定半徑範圍裏面，那就會產生的干擾，那假設 A 的無線電干擾範圍是這麼大，傳輸範圍是這麼大，那同時你讓 C 把資料送給 D ，對 D 來講他是干擾，他收不到，因為他跟 A ，他也收到 A 的訊號，也收到 C 的訊號，所以干擾。那同樣的， F 也是同樣的狀況，同時也收到 F 的無線電訊號，同時也收到 D 的無線電訊號，他也是干擾的況狀。那有沒有一個方式可以讓 A,B,C,D 跟 E,F 同時傳送資料呢？那我們可以這樣作，那麼我們發現 A 希望把資料送給 B 的時候， A,B 的距離不是很遠，所以 A 只要縮小他的傳輸，無線電傳輸距離喔，那可以省下很多電力，無線電的傳輸幾本上是跟距離的 a 次方成正比， a 可以得到 5 ，所以那是 ... 不是，不只是距離成正比，而是根距離的 2 到 5 次方成正比。所以當我們能夠把傳輸距離縮小的時候，我縮小下來了這個 ... 我省下了這個功率幾乎是距離的 a 次方，最少 a 平方，這時 A 可以省下很多電，那因為我 A 把這個無線電傳輸距離縮小了，那所以這個時候， F 就收不到 A 的訊號了， B 也收不到 A 的訊號了，那所以同時 A,B 跟 C,D 和 E,F 三組傳輸就可以同時進行，這個就是無線電裡面一魚二吃的最好例子。那既省電，而且又可以同時增加彼此的 space efficiency ，就是空間上更多人可以同時傳輸。好，那這是第一個，大概有一類就是做這種 transition power control 的，那我只是隨便舉個例子喔，大概還有很多不同的研究主題，不同角度省去能量，這是一個。
MAC layer 的省電例子：關掉無線電，週期性的開啟無線電以便接受訊號
好，那第二個就是剛剛講的 MAC layer ，媒體存取層，那就是 ... 我們同樣舉個例子喔， A 正在送資料給 B ，那問你說， C 有必要保持醒著嗎？譬如說， C 有必要把無線電打開嗎？那我們的答案是 no ，因為 A 正在送資料給 B 的同時，那其實這個時候 C 也不必醒著，因為他也收不到，那同時 C 其實也不能把資料送出去，因為他一送資料，他也會干擾到 B ，那所以他不能收也不能送，那就不用醒著，那不用醒著就可以永遠不用醒著嗎？所以我們會把他的無線電關掉，但是你隨便把一台設備的無線電關掉，那你要讓它週期性的醒來，以便能夠等一下萬一喔，這個 A 跟 B 的資料已經傳送結束以後，那 A 這時候他要送資料給 C ，剛剛 C 看到 A 正在送資料給 B 阿，他就把無線電無窮無限期的關掉，那萬一等下 A 有資料要送給 C ，那 C 不就是沒辦法收到了嗎，所以他一定要週期性的醒來，把無線電打開，然後看看有沒有訊號進來，是要開個封包，所以這個就是一個所謂 mode ， active mode management 。那無線電關掉，進入省電模式，大概只要用二十分之一的電力就夠了，但是我要週期性的把我的無線電打開，短期的進入 active mode ，以便能夠接收到正好有訊號進來，那這邊有非常多的研究在這邊進行。
network layer的省電例子：利用不同的routing algorithm找到最適合的傳輸路徑
那我們再看 network layer ，這邊有一個例子喔，這裡有一個 source node ，我要找一條路徑透過 multihop path ，把我的封包送到 destinaiton ，所以從 S 送到 A ，那很明顯的，正好有條綠色的 path 是三個 hop ， one hop,two hop,three hop ，以下也有一條紅色的 path ，也是三個 hop ，好，那我們會選那一個路徑來送？那就會有很多選項了，那在我們這裡面呢，可能會，有些演算法會說不定會選這條路，那他的理由是什麼？因為這裡面呢，每一個中間節點電力都是還是比較充足的，好那為什麼不選上面這條路徑呢？那因為這個路徑裡面，這個設備的電力已經非常不充足了，那幫忙轉送幾個封包之後，他可能就 ... 電力用完，他就掛掉了。好，那我們在網路上，通常會有一個 .. 在多跳網路上，通常有一個節點掛掉的時候，常常會使整個網路的連通性消失，所以在 criteria 之下，我們希望選到這條路徑。當然你可以有不同的 criteria ，那有時候有些 criteria 可能會會選這條路徑，而你的著眼點是省能，就是走耗電量較小的你可能就會選這條，可能這裡是三公尺，這裡是三公尺，這裡是五公尺，總耗電量比較小你會選這條路，那這條路可能這裡是十公尺，這裡是二十公尺，這裡是三十公尺，那傳輸距離比較遠比較耗電，總耗電量比較大，你有時候就不選這條，所以不同的 criteria 會影響你的路徑的選擇，還是以你要採哪一個 criteria 去看，那你也可以一起考量，那麼這邊也有一堆 research 做這個研究，所以可以考量一下去找些 related paper 去看一下，假如你有興趣的話，你等一下，剛剛講說做省電，無線通訊隨意網路，隨意網路上面省電大概省了三倍， phisical layer,MAC layer 和 network layer ，那我們今天 focus 在 MAC layer ，就是做 power management ，有時候我們把無線電關掉，節省一些電力，當我們不用傳訊傳輸訊息的時候我們把無線電關掉，省掉一點電力。
無線電關掉電源是最省電的方式，但一直關會收不到訊號
好，那我們看這個把無線電暫時關掉有什麼好處？這是一個實際的數據，我們採取這個 no call ，當這個網路卡在 11Mbps 的時候，在工作，我把無線電暫時切入省電模式或是睡覺模式，你只要耗掉 60mW ，千分之六十瓦特的功率就好了，但是只要你一把無線電打開，那不管你是在送資料，在收資料或者只是把無線電開著，在那邊等人家 ... 監控有沒有無線電訊號進來的話，至少也要 805mW ，所以你可以比較一下，一個至少有 ... 最多就可以差到 20 倍，那就超過 20 倍，那這裡至少有幾倍的差距， 有到 13 倍以上的差距，所以無線電關掉對他是省電的事情，或者換句話講，把無線電設備傳輸的模組是很耗電的單位、很耗電的模組，沒事就應該把他關掉。但是我們不能一直關阿，一直關會收不到，這是他的缺點。
802.11 的省電控制設定
所以 802.11 他本身就有一些設定，所以我們剛剛看到上面的動畫，注意一下他是同步的。每個設備的時間是對話時間，對話時間我們講一秒鐘大家醒來一次，大概在內部時脈每一秒的開頭就會把無線電打開打開十分之一秒，規格是這樣定義的，每個設備定好時間之後，就每次一秒鐘為單位，一秒鐘到的時候，就醒來十分之一秒，其他的十分之九秒就回到無線電關掉的省電模式回到 synchronize mode 。
把 synchronize mode 搬到多跳環境的問題
當然 synchronize mode 有一些問題，當我們把 synchronize mode 搬到多跳環境的時候就會產生一些問題，剛剛忘了提 synchronized mode 是用在單跳的環境，單跳環境有一個好處，剛剛講過就是作為一個節點廣播一個封包叫大家定時、對時，大家的時間都一致，所以他的 synchronize 比較容易做到。當然我們把單跳模式的這個省電通訊協定搬到多跳的模式，對時就變的很困難。所以就需要非同步的一個通訊協定，等一下有別的投影片會講的比較清楚。
Beacon 的介紹
所以在 802.11 他有自己定義的省電通訊協定，他可以做單跳的省電控制，但是在多跳就需要用到非同步的，但不管單跳或多跳都需要用送 Beacon ，訊標，或者叫信標，信標作對時跟做一些有沒有資料量傳送的控制，什麼是 Beacon ， Beacon 在無線電設備裡面是很普通的零件，無線電設備因為沒有實體的連線，必須不時的送一些訊號來告訴其他的無線電設備說我在這裡，我有一個無線電頻道可以來跟我連線，所以無線電設備裡面 Beacon 是一個很重要的一個訊號。在 802.11 的省電方面協定裡面還有一個很重要的功能是 to synchronize clocks 所以大家可以把無線電塞一個 clock 收到以後大家就互相對時，所以這是 Beacon 的作用。所以 Beacon 在無線電裡面很重要循環通知別人我在這，通知別人可以對時了。
802.11 如何用 Beacon 來對時
那 802.11 怎樣用 Beacon 來對時呢？剛剛講過，他把時間切成一秒一秒的為單位，每一個單位稱為一個信標週期，對每個信標週期他會送一個信標出來，所以每一個信標週期開始呢，叫做 Beacon transition time ， 每個信標週期一開始準備要送出信標了，跟發光一樣，光走一圈很多量子，量子有週期的。一堆人一堆設備，比如說一堆人在同一房間裡用 notebook ，現在都是 one hop 這些設備都在省電模式底下，一秒鐘後時間到了大家都要搶著送出信標，假如大家都送，那大家都通通撞在一起，所以一定要有一個機制，讓他能夠把信標只有一個人可以成功傳送，所以他的第一個動作就是，每個人都會選一個 random back off time ，一個隨機後退時間，所以我可能選 8 ， 連 老師可能選 2 ，所以在一開始的時候大家都會後退一段時間，我選到 8 有 8 個時槽， 那連 老師選 2 有兩個時槽，在我等待的中間，假如沒有收到 Beacon 的傳送，等到我 8 的時間到了，就不能送了。那如果我選 8 ，我等到 2 的時候， 連 老師他在 2 的後退時間發現 0 和 1 都沒有人送，他其實在第 2 個時槽就送出 Beacon ， 那連 老師送了 Beacon ，當然我就接受到 Beacon 當然我在第 8 個時槽就不送了。所以每個人都隨機選一個後退時間，所以只要是節點數夠不會太多，後退時間夠分散的話，基本上，大概大部分的時刻都只有一個 Beacon 會成功傳送出來，而且傳出來大家都收到了，那這個例子裡面只有兩個節點， A 送出來， B 收到了，那 B 收到以後呢，就會透過一個 time synchronization function 去把他做時間同步。那同學有沒有注意到這其實是 one hop 很好做，因為 one hop 大家都在彼此的無線電傳輸範圍內，只有一個節點會送出 Beacon ，大家會根據那個節點的 Beacon 來對時，裡面會塞一個時間資訊，所以就把大家的時間都同步了。
所以一秒鐘對錶一次，那 802.11 的誤差，出槽的誤差上限是 200bpm ，就是一百萬秒才會誤差兩百，所以一秒對一次誤差就會很小。所以大家時間都會很準，一秒對錶一次。所以假如送 Beacon 的時窗裡面大家把無線電打開了送 Beacon ，收 Beacon ，等看看有沒有任何人要收送資料，假如都沒有任何的訊號出來的話，就表示沒有人有送資料，所以我就可以進入 power saving mode ，進入省電模式。所以我十分之一秒無線電打開，收 Beacon 對錶，然後呢，假如沒有任何訊號要送給我，我就進入省電模式，所以我有十分之九的時間進入省電模式，用大概二十分之一的電力維持。我有十分之一的時間收送 Beacon ，大概百分之一百無線電打開來維持，所以這就是他的省電量。大概這個省電量就會像剛剛一樣達到十分之九的省電，可能比十分之九還少一點，大家可以算一下，因為這裡還有二十分之一的電力要維持。那假如每一個一秒鐘，第二秒鐘開始，大家又搶著開始要送 Beacon ，同樣的，基本上有很大的機率只有一個人會傳送成功，那每個人就跟他對錶，那不要擔心 A 的錶跟 B 的錶會差很多，不會！因為剛剛一秒對一次，偏差是 200bpm ，不會差太多，所以誰送 Beacon 對錶都沒關係，都會把他對的很準。
那 Beacon 送完以後，大家還是維持在十分之一這樣一個無線電的狀態之下，這個情況下，在這個例子裡，假如 A 有資料要送給 B 的時候，會發一個通知給 B ， B 因為正好把無線電打開，會收到並會回一個訊號，代表只經知道了。從此以後， A 和 B 這兩個就會進入無線電打開的模式，那說要送的人就不能睡覺，那其他人能不能睡？其他人還是可以睡，所以這個圖沒有畫出來，假如有 Host C 、 Host D 等等就可以去睡了。所以只有送資料的人跟收資料的人醒著就好了，他們就在剩下的十分之九秒把封包送出來，這是綽綽有餘的。所以這就是 802.11 的省電通訊協定，這樣就可以 work 啦。所以你們現在的筆記型電腦上 802.11 的隨意模式切成這個模式還可以切省電模式，或是照這樣的模式來運作，是真的可以 work 。
802.11 的 clock synchronization 用在多跳模式所付出的代價
那我們就開始做研究了，我們發現 802.11 這個省電模式適用於 single hop ，當然有些 hop 是對他省電，可以同時睡同時醒，但是有些缺點，用 clock synchronization 就是把他用在 multi-hop network 會很花代價，花很多的控制去達成，或者甚至於是做不到的。假如這個做不到的話，那網路就會有很多的狀況。有一些研究就是當你把 802.11 的省電通訊模式用在很多節點的狀況之下是不 work 的。為什麼不 work ？當 Beacon 送出去大家都撞在一起，太擁擠了，節點超過兩百就不用了。儘管如此，這也是有些事先知道的事實，那我們在做這個研究的第一步還是嘗試把 802.11 的單跳模式先做 clock synchronization ，所以我們做了一個模擬，我們把 802.11 的單跳的通訊協定寫好模擬把他放到多跳模式去跑，發現 clock 的誤差，就是最快的和最慢的偏差，大概我們一跑這個單位是一個 Beacon interval 在這個例子是 0.1 秒就送一個 Beacon ，所以跑到這裡 250 秒他的誤差已經是 1500 個 microseconds 以上，所以其實我們這個時間一跑的時候就跑到 500 個 microseconds ，最快的 devices 和最慢的 devices 就差這麼多了，本來是同步的，把他放到裡面去跑就變不同步了。而 802.11 的規格裡面呢，所有的 devices 要正常的收送資料的話，誤差範圍要在 200 m icroseconds 裡面，所以我們這個實驗告訴我們多跳環境用同步的方法來做根本是不可能，已經超過標準太多了，只要求在 200 個 microseconds 裡面，最快跟最慢的最慢的差一下就超過 200 個 microseconds ，甚至到達了 2000 個 microseconds 以上，所以這個實驗告訴我們這條路不可行，所以就嘗試著走第二條路。
clock 不同步的另一個問題 - network condition problem
當然這個 clock 不同步就還有一個問題。當這邊有一個 one hop 的 network ，這邊有另外一個 one hop network ，本來是在不同的空間上獨立運作，假如這三組、這三個人，紅色的這三個人往左邊移動，就構成新的 network link ，以後呢，他的實體上已經是一個網路了，但是在實際狀況下他們是聯絡不到的。就是假如這三個人在 power saving mode 在省電模式下構成 one hop network ，當這兩個網路互相接近的時候，他們本來是分開的，互相接近的時候他們有一個實際的無線電鍊節，都在彼此的無線電傳輸範圍，但他們無法知道對方的存在。原因是為什麼呢？因為剛剛我們單跳的時候通訊協定、省電通訊協定，每一秒鐘醒來一次， 0.1 秒無線電打開， 0.9 秒無線電關掉，那我們剛剛不是講，我們都是靠 Beacon 來知道對方的存在嘛，所以當紅色的人，在他醒來的時候送出 Beacon ，或者藍色的人在他的無線電範圍有時候也會送出 Beacon ，正好紅色的或藍色的他們都是把無線電關掉，所以永遠不知道那裡有一個無線電就在旁邊，所以在實體上他們是在彼此的傳輸範圍之內，但實際上他們是分隔兩邊的 network ，這就是 network condition 的例子，彼此不知道對方的存在，這個叫 network condition problem 。
所以我們把這幾個問題整合在一起，就是我們要解的問題。就是在多跳的環境之下，要做省電只好採取 asynchronies 的方式，所以我們最後採取的策略就是 solve the network condition ，我們為了解決這個 network condition 問題，就是說彼此不知道對方存在的問題。當然解決這個問題代表能做到什麼，就是能做到 network discovery ，就是我有個鄰居在旁邊送 Beacon ，我馬上可以知道，即使無線電關開跟他不同步，我都能夠知道，而且之後我就可以做情形預測，只要能夠知道他的存在，從此以後，我把要知道這些無線電設備到底什麼時候才會打開，以便於我可以把資料在他無線電打開的時候送過去。所以我們解決的問題，就是我們一開始動畫的第二個例子，你睡你的，我睡我的，但是我們約定，我們要在指定的時間裡面應該有一段時間是剛好我醒來的時候你也醒來， Beacon 送出去你收的到， Beacon 送過來我也收的到。
何謂 Quorum?
在文獻上有三個 protocols 已經做到這個動作了，這是交通大學 曾煜棋教授做的 。其中有一個最省電的稱為 Quorum-Based power saving protocol ，這就是我最早注意到這個通訊協定的起點，因為我博士班的研究就是做 quorum 理論上的研究，有人用這個名詞來命名這個通訊協定，特別注意了這就是我們今天？？那什麼是 quorum ，根據牛津字典， quorum 就是法定人數，我們開會一定要超過法定人數才能開，譬如人數的 2/3 ，最常見的法定人數是 1/2 ，今天假設全系要開會過半數的人出席就可以開的話， quorum 叫做 half members 。投影片的漫畫裡面說我們不能在裁員了，我們已經沒有法定人數可以開會了。後面還有一個漫畫，有一個打掃的歐巴桑也參加了開會這樣就達到法定開會人數。所以 quorum 就是一個開會的法定人數。再重新回來， what is quorum ？當然 quorum 這個字眼在數學上已經被借來當一個量來使用，就是互相相交的一個集合。這樣說好了，假設我們全系的同學都去開會，有不同的委員會，有一個旅遊委員會，有一個學術委員會，每個委員會都要過半人數才能開會，那請問各位同學有沒有可能同時召開旅遊委員會和同時召開學術委員會？答案應該是不可能，對不對，因為既然兩邊都要過半數才能開會，所以一定有些人要同時參加學術委員會又要參加旅遊委員會，那我們假設不能開會到一半跑到別的委員會開會，必須留在那個委員會裡面，任何一個時間一個委員會可以開，所以 quorum 裡面隱含有什麼樣的味道？就是交集。所以當你委員會都互相有交集的時候，就是任何一個時間只有一個 quorum 能夠成立，只有一個委員會的法定人數可以成立。所以數學上就把 quorum 這個交集特性把他抽取出來。假如你們公司只有三個人，法定人數是過半數的話，那麼 1 、 2 這兩個人， 2 、 3 這兩個人， 1 、 3 這兩個人都可以構成法定人數，可以看到都是互相相交的。過半一定相交，相交的特性就是數學上 quorum 的使用，所以當然後面跟數學有關的就是相交的特性，大家知道一下。
如何用 Quorum 來解決多跳的省電問題。
那我們的 quorum 怎樣解決多跳省電問題？我們首先把剛剛那個 quorum interval 一個一個編號，從 0 編到 N-1 ，然後再從 0 編到 N-1 ，在這個例子 N 有 16 個，編號以後呢，把這個陣列排成 √N*√N 的陣列所以這是 4*4 的陣列，然後我們排成陣列以後，隨意拿一個 row 一個 column 當作我們的 quorum interval ，就是我們這邊有 16 個人，那我們的法定人數就是隨便找一個 row 編號的人出來以及一個 column 的人出來，在這個例子是 2 、 6 、 8 、 9 、 10 、 11 、 14 ，就是我們的 quorum
interval ，法定的週期。那我們在看這個例子所以這個藍色的部分就是一個 row 和一個 column 都是所謂的 quorum interval 。那我們注意到什麼，我們再把他還原，會注意到剛剛的 quorum interval 拿一個 row 和一個 column 一定會在兩個地方相交，在兩個地方有交集，所以這就是為什麼用 quorum 這個字眼的原因。剛剛這個集合 0 、 1 、 2 、 3 、 5 、 9 、 13 跟 2 、 6 、 8 、 9 、 10 、 11 、 14 ，會有交集，所以在這個例子是兩個交集。那我們把這個還原為原來的時間軸，藍色跟紅色的把他還原，我們發現有兩個交集。那假如現在 Device 無線電的開跟關是下面的這個情況，就是被選為 quorum interval 的開關要打開，不被選為 quorum interval 的無線電可以關掉的話，只要我用 quorum interval 這樣一個 row 和一個 column 的一個選法，兩個 Device 之間至少會有兩個時段同一個無線電是同時打開的。所以即使你睡你的，你醒你的，我睡我的，我醒我的，但是我們一定在 16 個 Beacon interval 裡面會有兩個都醒來的，這樣不就是可以互相聯絡了嗎？剛剛我舉例是為了簡單啦，其實這個 802.11 一個 Beacon interval 是 0.1 秒，所以 16 個 Beacon interval 是 1.6 秒，即使 N 取 16 ，就是在 1.6 秒裡面，可以聽到附近的無線電設備的信標兩次，所以平均的鄰居發現時間只有 0.8 秒，這是合理的，就是一個無線電打開了，在 0.8 秒內就可以發現他的存在，可以跟他通訊，這是可以忍受的一個延遲。那剛剛我們講至少有兩個 Beacon interval 會相交，但是我們現在討論的不是同步的環境，而是非同步，而且還有一個狀況，你的 Beacon interval 編號 0 ，我把他編號為 8 ，所以大家的週期是不對齊，我的 1 是你的 0 ，你的 0 是我的 1 ，或者會多更多，有任何的位移偏移的問題，沒有對齊。 然後我們是 rotate ，那因為我們是循環編號，所以這邊可能是 13 ，一邊是 14 、 15 ，所以我是循環編號，沒有對齊，那沒有對齊你看，在沒有對齊的情況下，不管你怎麼挪喔，還是兩個以上的交集，所以這就是一個技術的厲害的地方，只要把一個 quarter 這樣取，把一個 room 開了，那即使你沒有對齊也沒關係，偏移一個位置，還是有價值，偏移兩個也有價值，考慮三、四個，不管你怎麼偏都會有價值。
省電機制的說明與分析
那當然這個偏移是整數偏移，整個 beacon 的偏移，那我們非同步還要考慮什麼，就像剛才我們剛剛動畫的過程，每一個移動的點上面都有可能是不同的 device 的時間的起點，所以我們這個是不是完全的不對齊，好所以這個時候我們只好去修改 quorum ，看它那個通訊協定的 quorum structure ，所以我們的 quorum interval 裡面就是會這樣修改，就是會改成一個 beacon window ，還有一個這個 eighteen window ， eighteen window 跟剛剛那個 802.c 的 eighteen window ， eighteen window 就是類似我用來送 beacon ，用來看看有沒有訊號的時候，有訊號的時候要把封包給我，那在剛剛 802.11 的結構裡面，是 quorum interval 的，也就是說你這個非省電模式的，它只有一種格式就是 eighteen 、時窗，十分之ㄧ的時間可以使用十分之九的時間可以進 power saving mode ，只有一種格式，那在我們的 quorum interval 的結構裡面就要稍微修改了，在一般省電模式的時候，你還需要醒來一小段時間，那醒來多少時間？醒來一個 eighteen 的時窗，這個 eighteen 時窗可能是十分之ㄧ，或比較小的我們就二十分之ㄧ，那另外呢，在 quorum interval 的時候，可能會有大概二十分之ㄧ的這個所謂的 beacon interval 專門用來送信標，然後一樣有十分之ㄧ，到二十分之ㄧ這麼小的時窗呢用來一樣送 eighteen 訊號，然後這裡是不一樣的地方喔，在比較可以稍微背一點的就是，它在被你選為 quorum interval 的時候，在後面本來這個省電模式可以進入到完全省電的時候呢，你還要打開你的無線電做監控模式， mode inter-mode 那其實這一段 mode inter-mode 呢，就是為了處理像剛剛我們前面介紹的這個細微的偏移，所以到我們把結構這樣子修改，多花一點點電力，讓你可以不必做同步，而且也可以在任何時刻可以證明，我只要在一個 round of n 的 beacon interval ，在一個 round ，在這一輪裡面的 beacon interval 時，我就可以聽到對方的 beacon 兩次，也就是任何 device 只要互相接近，那你在你的 quorum interval 就會送出信標，那我因為有這種 quorum interval 完全進入無線電開啟的情況，就可以證明說，它在 a round of n 個 beacon interval 的時候那你就可以聽到比次的心跳兩次，那像剛剛我們的例子裡面，假如是十六個 beacon interval 那不是 1.6 秒可以聽到彼此的心跳兩次，那平均就是 0.8 秒就可以聽到了，所以這個就是 quorum interval 的一個使用，來做省電通訊協定，來做這個 neighbor discovering 鄰居發現，我們就可以知道鄰居發出信標，那鄰居送出信標以後我就可以根據信標上面的一個時間戳記來看醒來的時間有多少的 offset ，我本來是一秒起來，結果它醒來的時候是我的 1.3 秒，你就知道它醒來的時間跟我會有 0.3 秒的差距，所以未來我要把資料送給對方的時候，就要加上那個 0.3 秒的差距，預期對方在每個週期一定會有一小段時間醒來，我就會把那一小段時間裡面，送出我的 eighteen 訊號，這類似就是 802.11 的 ap 訊號，就是有一個資料傳輸的控制給對方看，對方就會以同樣方式醒來然後傳送過去，好所以這個就是一個省電機制，就是我資料要送你才會醒來，沒有資料要送你就不要醒來這樣的一個機制。
Quorum System 與 Quorum interval 的構成條件
好，那所以網路就可以正常 merge ，那因為你們這裡有一個有時候有些人會進入 quorum interval ，那進入 quorum interval 會稍微費電一點，因為無線電還是保持在監控模式，可以讓你知道對方的存在。好那剛剛那個證明，在一個 round 就是 n 個 beacon interval at 讓彼此的 beacon 兩次，那原來這個 許 教授在這邊證明，他證明了兩頁，那後來呢我就把它 model 成一個 quorum system ，那證明只有兩段話，兩個 paragraph ，告訴我們數學的 model 讓我們把事情簡化得更清楚，所以我用 quorum system 來幫助證明，我們把剛剛那一大個 quorum 把它收集起來， collection of insuring intersecting subsets of interval set 那就成了我們的 quorum system ，好所以那剛剛我們看到有一個三個人的集合裡面， 1 、 2 ， 2 、 3 ， 1 、 3 ，都是所謂的法定人數集合，那你把這些所有的法定人數集合都收集起來，所構成的這個 collection of subset 那就成為了 quorum system ，就是一個法定人數系統，那也就是說假如我現在有一個 quorum system 的 image ，那 quorum system 裡面呢每一個 quorum 都可以當作你選擇 quorum interval 的依據，比如說像剛剛我們有一個 u = 0,1,2,3,4, 到 15 ，表示我們的 quorum interval 的編號 1 號 15 ，好那我們剛剛步是有拿一個 row 一個 column 嗎，那一個 row 一個 column 的拿法裡面的排列組合有非常多，包括我們剛剛舉的例子裡面， 2,6,8,9,10,11,14 ，這是一個 quorum ，這也是一個 quorum ，那這兩個 quorum 兩兩 相交，那你把這所有可能的組合把它列出來，那這就是一個 quorum system ，那數學上就可以做這個全列的這個動作，那我們就用這個來證明喔，用這個 quorum system 來證明，這個少量的兩段話，那但是我們其實注意到，不是符合相交特性的 quorum system 就可以用來證明，所以我們還需要一個什麼特性，一個 rotation closure property ，剛剛有一個動作就是，我的 quorum 有一個編號，即使有旋轉那旋轉以後還是要可以跟其它的 quorum 相交，這才可以用。
證明 Quorum System 與 Quorum Interval 構成條件的正確性
所以我們就 invite 了一個叫做 rotation closure property ，利用這個 rotation closure property 的特性套到 quorum system 之上，好那然後才可以證明，不管他怎麼偏移都可以相交，那在這個 property 之下呢，我們開始去追求喔，首先我其實是想看看，這一個 李 教授的這一個演算法是不是有最佳化，所以首先我最佳化我首先就是要探討它有沒有所謂的最佳值，那最佳值什麼叫做最佳值，就是我隨便給你一個 n 那你能不能告訴我，我 n 裡面最少要挑幾個成為 quorum interval 就可以保證它們 兩兩 相交。好我挑太少不好，挑太少不容易相交，挑太多呢太耗電，因為你看看剛剛 quorum interval 的結構被我挑到 quorum interval 的它就永遠無線電要打開，所以我挑太多太耗電，挑太少則不容易有相交，隨便一偏移一旋轉就不相交了，好那的確當我們發現這一個特性的時候，我們一種兩極化的需求出現，變多太耗電，變少不容易相交，違反這個在一個 round of interval 裡面要彼此聽到對方的 beacon 一次以上，那所以我們就找到一個 lower bound 來證明滿足 rotation closure property 的這個 quorum system 裡面，它的 quorum size 至少是 k 以上， k 要滿足 k * (k – 1) + 1 ，而且 k – 1 必須是一個質數的指數次方，所以這個也用到了質數的指數次方，好那所以我們證明了這樣的一個 lower bound ，那基本上這個花了很多時間去證明這是個質數的指數次方，那我們花了很多時間去證明出來阿，所以我們知道說你用這種技術來挑 quorum interval 假如要最省電，最省也只不過是如此，就是 k ，那我們有 lower bound 求出來以後，我們首先可以肯定的就是 曾 教授的那個演算法沒有達到最佳化，那是一個若一個 column 那每個若是那其他算出來是一個 column – 1 所以您這個很接近根號 2a 但是比根號 2a 還大了兩倍，那沒達到 optimal 那我們就開始去找有沒有一些 quorum system 是 optimal 的，那我們開始找阿，我們找到了一個，那運氣不錯， 1985 年有個日本人叫「馬呀咖哇」他提出了一個叫做 finite projected quorum system ，它的 quorum size 正好跟我們求的那個 lower bound 的式子完全一模一樣，我們很高興，式子一樣那表示有機會啦，好那我們後來去驗證啦，的確它也滿足 rotation closure property ，那它的 quorum size 跟我們的這個 lower bound 完全一樣，所以我們找到了一個 optimal solution 的 optimal system ，那當然我們還不滿足啦，雖然這個 optimal 很難找啦而且它的條件比較嚴，那有沒有一些 near optimal 的也可以就是 order 根號 n 等級的，那我們發現有， 那曾 教授所使用的那一個把大家排成正方拿一個 row 拿一個 column ，那也是 1985 年「馬呀咖哇」也提出來過的，他把它稱為 grid quorum system 格子點，把大家排成格子點拿一個 row 一個 column 那他是 2 根號 n 減 1 所以它是 near optimal ，好那我們就發現還有 torus 還有 cyclic quorum system 還有我們自己提出來的一個叫做 extended torus quorum system ，它就是根號 n 等級阿，也就是所謂的 near optimal quorum system ，好所以這是我們第一個 work 。
探討 Quorum System 省電的效果與運作情況
對於只用 quorum system 來解決省電問題，我們推導它的最佳化的狀況把它求取出來。好那剛剛我們講的那個 quorum base asynchronize power saving protocol ，它有些好處，當然也有些缺點，好處是不用同步，好處是可以使用多跳使用，好處是它在不用同步的情況之下就可以達到 dual discovery 也可以做到 wakeup prediction ，當然缺點是什麼，我們發現它還是比同步的省點通訊協定多耗了那麼一點點，因為我們剛剛看到它那個邏輯架構上，剛剛這個是同步的，所有的人都是十分之ㄧ還有無線的 hand switch 也就省電，那在這個 quorum base 裡面，大概省電的地方就是這裡比較接近， non quorumable 省電的提議這個同步的接近，但是在 quorumable 我要永遠把無線電打開，而且我的 quorum 跳出來至少有什麼一個大的這個跳出來，所以稍微會費一點的電，剛開始比較費電，那有沒有可能把它結合在一起，比方有個 draw back 很費電，而且我們發現他在高高密度的時候其實也會有這個有的 beacon 的衝撞啦，就是有人正在送資料的時候我突然醒來這 beacon 就丟出去了，就撞到那正在送的，那所以在高密度的時候也不適合使用，那所以有沒有辦法有一個機制可以去除這些缺點，讓他更省電一點，讓他在高密度的時候也可以用，那我們就繼續做以下的研究。
探討結合同步與非同步省電通訊協定的利弊
一個 hybrid 混合式的 power saving protocol ，那省電的把這個同步的跟非同步的把它混何在一起，好那我們 hybrid 這裡呢就是做了這樣的一個動作喔，把這個省電的也用，把這個同步的也用非同步的也用，那同步的就用 802.11 的單跳模式來使用，那非同步的部份呢就用這個 quorum base 的什麼來用，那同步的要用 802.11 那我們知道 802.11 只能用在單跳阿，好那我們就想到一個方法用 clustering ，我們就用叢集式的，那有一些人就管單跳的這個範圍，也就是我們這個同步模式，好那這個非同步的這個地方呢在用這個所謂的 asynchronize 的模式，那我就可以更省電了，好我們看圖比較快，什麼叫 clustering ，這裡不管是黑色的或者紅色的部份都是無線電設備喔，那我們讓紅色的無線電設備是所謂的形成一個 cluster ，好那我們每一個 cluster 叢集裡面，這是一個 cluster head 它就管一塊區域，這一塊區域就是它的 cluster member ，阿所以 cluster edge ，大家就跟他是對講，所以這一區呢就由這個 cluster head A 來管，那這一區呢就由這個 cluster head B 來管，阿所以他們都是 single heart 嗎，所以都是用這個單跳的這個同步的省電通訊協定，然後呢，關於我的資料要傳很遠，那我再透過多跳的這個方式呢來把資料送出去，所以在這個多跳的地方我再用這個非同步通訊協定來處理，因為我在多跳的地方，這個 head 跟這個 head 、跟這個 head 、跟這個 head 他們的 clock 是很難同步的，那我就採取多跳的非同步通訊協定，好那我們知道非同步比較耗電嗎，但是我的 cluster head 數目很少，所以我讓那個比較耗電的在少數的 cluster head 上執行，然後把比較省電的通訊協定在大部分的 device 上面呢來實施，好所以就可以把兩邊的好處做整合在一起。
探討系統的穩定性與正確性
好那還有引發一些問題，我們把大家做 cluster 以後呢，你還要先保證一件事情就是，首先我要先確定怎麼樣把這些 cluster 建構出來，建構出來以後呢要先保證一件事情就是， head 跟 head 之間呢是要聯絡的上的，好因為 member 跟 non head 是做什麼常常是無線電關掉的，幾乎是不幫忙做通訊的，所以 head 跟 head 是要聯絡的上的，那所以我們要做一些機制阿，我們用了這樣的一個機制就是，我們讓 cluster head 跟 cluster member 是採用不同的轉速半徑，所以我們讓 inter cluster ， head 跟 head 之間是採取遠程的比較長的傳輸距離，而讓我們的這個 head 跟 member 之間是一個短距離，那這樣有什麼好處呢，我們讓每一個 head 他們加起來的距離，這個 head 跟 head 之間比較長的距離保證一定連得上，我們後面會有一個證明，那設定好一個 rv 跟 ra 的關係之後保證你所構建出來的這個 cluster head 絕對是連通的，這是第一個採取雙重的 transmission language ，那第二個呢，我們採取 dual channel ，因為很有可能有一個狀況，就是這個 head 跟這個 head 在長距離傳輸的時候，那或者我這個旁邊有一個 a 正在做長距離的傳輸的時候，雖然他不是送給 e 的，但是它的無線電長程傳輸的覆蓋範圍很大，那這個時候我可能有一個 e 的跟它底下的 member 我們叫它做 h 好了，在做傳輸，所以一個長距離的一個 head 之間的傳輸會干擾到短距離的傳輸 head 跟 member 之間的傳輸，所以我們不希望有這樣的一個狀況，所以我們做這個動作，我們用 dual channel 兩個 channel ，長距離的傳輸用 a channel ，短距離的傳輸用 b channel ，所以當有一個跟我不相干的長距離的傳輸的時候，我依然可以用其他的 channel 跟我不涉入其他長距離傳輸的 member 它的 head 來做傳輸，所以我們採用了這個 dual channel 的這個技術，所以這樣子我們可以善用我們的空間的共用性跟頻道的共用性，所以我們採用了這兩個技術。所以剛剛的 dual channel 跟 dual transmission range 都出現在我們的論文的開頭裡面阿現在這裡做一個講解，一開始我不念阿因為太長了，這裡我就把它講解完了，提供兩個 channel ，那兩個 channel 以後我們跟剛剛一樣，用 detect 無線電主要是無線電省電通訊協定，我們就有分兩類的應用，一類 beacon 呢叫做 intra cluster beacon ，另外一類呢叫做 inter cluster beacon ， intra 就是往內，往內呢就只有我的 cluster head 用比較特別的 channel b 送比較小的距離，用來照顧我的 member 。那另外一類呢是為了要遠程通訊用，用 channel a 用比較大的傳輸距離，這是為了跟其他的 cluster head 通訊用，兩種 beacon 一種是照顧 member 一種是 cluster head 拿來跟其它的 cluster head 做通訊用，那我這裡其實這個 beacon 是用來採取 asynchronize 非同步省電通訊協定，就可以做到 wakeup prediction ，可以做到 another narrowing cluster head discovering ，那這邊這個 intra cluster beacon 是用來做 cluster forming 來照顧我的 member 所以我當你的 head ，我還在這裡，你不要你也跳出來當 head ，一個 head 就好了，可以做 cluster quantization ，用 synchronize power saving protocol 做 cluster quantization ，所以我要有兩種型態的 beacon 。
探討系統的實用性，與現存技術的整合
好那我們把他這個從現實生活上考量，這樣子假設對不對，把這兩種技術加進來會不會太牽強，所以我們實際上來考量， 802.11 可以讓你來做 power control ，所以我可以控制我的傳輸距離、傳輸功率，當然傳輸功率可以換算成傳輸距離，所以這是可以的，第二個你假設多頻道的傳輸合不合理，這也是一個，我們 802.11 其實有 13 個頻道可以隨時切換，我們平時沒有切都選擇自動模式，自己再按掃描來看哪一個頻道可以用哪一個頻道可以碰上去，那其實它是可以設定的，有 13 個頻道可以設定，這 13 個頻道裡面可以同時傳輸，只要你隔開 5 個號碼，也就是說 1 號、 6 號、 11 號它能夠隔開 5 個頻道以上就不會互相干擾了，所以我 13 個頻道裡面至少可以有 3 個頻道可以同時用，可以用 2 、 7 、 12 ，可以用 3 、 8 、 13 ，這三個是不互相干擾的，而且我們現在只要兩個就夠了，我們絕對沒有問題，所以我們這兩個假設是合理的。
介紹 cluster head 的功能、並如何選擇 cluster head
好，那這個合理了以後我們來看看，我們怎麼去做後面的 cluster head 的選擇。這個是一個漫畫，這個老闆被抬在那邊好高興喔，他以為是表現良好，結果不是喔，這老闆說他要提早退休了，那大家這個歡聲雷動，大家想太棒了，他太令人討厭了，大家都高興得不得了，好，那這只是一個小漫畫喔，我們只是把這個 cluster head 把它比喻成 boss 那這樣比較好講解，那我們來看直接來看這個喔，一開始大家這個網路裡面都沒有別的假設，每個人都是 device ，那誰要當 boss ，也就是誰要當 cluster head ，畢竟當 cluster head 有代價，你可能會，你要 pay ，你要付錢給你的員工，你要常常請客。所以不一定每個人都要當 head 。這個規則怎麼做？很簡單，就是無線電一打開以後，我會等待一段時間，這段時間裡面假如沒有人說他是老闆，那我就起而當老闆。那我當老闆以後就有負擔，我要定期的發出一個訊號說：「我是老闆」，照顧我底下的嘍囉。假如每個人講話的聲音有一個範圍，這個範圍裡面一個人當老大，其它人乖乖的當嘍囉。當嘍囉有好處阿，無線電可以關掉，等吃宵夜就好。當老闆有什麼缺點？我隨時要起來喊：「我是老大，我是老大」，而且我的嘍囉有時候還會叫我轉信給別人，送情書阿啥的都要老闆傳。所以說，一個圓圈、一個無線電傳輸範圍裡面，只有一個人會當老闆。利用這樣簡單的機制，可以把 host 挑出來，而且應該可以涵蓋所有的節點，因為沒人當你的老闆，那你就是老闆。你一定會聽到有人當老闆，那自己才不是老闆。沒人當你的老闆，自己才當老闆。所以說這樣的機制就能覆蓋所有的節點，很簡單的一個機制。所以一開始每個節點進入網路的時候，進入 listening mode ，等一段時間，聽聽到有沒有人說他是老闆，也就是聽到所謂 intra cluster beacon 。假如沒有聽到，那我自己變老闆，進入 cluster head state 。開始當老闆就有負擔，要經常的去廣撥我的 intra cluster beacon 。假如，我醒來一段時間以後，有聽到任何人說他是老大，那我就跟著他去，進入 listening state 。
Cluster head 的退場機制
當老闆有時候會提早退休，因為沒有錢，或者是被其它老闆幹掉，那 member 就沒有人照顧，所以呢，你的 member 其實會收集訊息，時間到了就會醒來聽聽看有沒有老闆請吃宵夜，有的話就跟他出去吃宵夜，沒有的話就繼續睡覺。所以我週期性的醒來，看看有沒有 intra cluster beacon ，有的話就繼續當嘍囉；都沒有的話，好幾次以後老闆都沒有發訊號說「他是老闆」，那趕快起來，就有一個人要取而代之了。所以連續幾次沒聽到 intra cluster beacon 的時候，我就要自行起來當老闆。這裡有一個 random beacon ，當我隔一段時間沒聽到有人當老闆，先進入 listening state ，以免當老闆離開時，所有的嘍囉一瞬間都變成老闆。所以說先進入 listening state 做準備，下一次準備當老闆，每個人都有一個 beacon time ，我們要大家互相禮讓一下，老闆退休了，那誰要當老闆呢？那我們要搶阿，搶一個時間，大家會選一個後備時間，我選八，連老師選二，所以就是連老師當老闆。所以大家有 beacon time 就可以錯開，老闆通常只會有一個。所以這個機制可以讓你的系統的老闆保持一定一個。但是有個狀況是，老闆在這麼模式底下只會多不會少，一個老闆跑了，被照顧的員工又會多一個當老闆，可是老闆跑掉了他還是老闆，所以這裡就有退場機制。老闆也是要退場的，什麼時候退場？老闆的退場就是，當老闆趴趴走，碰到別的老闆，像碰到理學院院長說：「我是老闆」，而剛其實是連老師當老闆，兩個人去吃東西，連老師說：「我要付帳」，陳老師也就是院長跟我們：「好吧，我來當你的嘍囉」，因為我們荷包比較薄，我們 priority 比較低，那我們就退了，說；「好吧，我們就退了，不當老闆了」，進入 listening state 當 member ，因為連老師轉過來了。利用這種機制，當我們發現收到另一個 cluster head 的封包，那我去根據無線電的強度，收到的強度訊號指示，計算出我跟那個老闆的距離多少。我們做模擬時，設為 1/5rv 的時候，就會分出老闆靠的太近，兩個人就要引退，或者不許老闆靠在一起，只要留下一個老闆。當然我們要定一些 priority ，老闆當越久的繼續留著， energy 比較少的就退掉。所以說老闆當越短的越不容易退，電量比較多，荷包比較充足的就不退，如果時間跟荷包都還有一定量就繼續當老闆，保證一群老闆靠在一起只會留下一個。這就是 class head 的退場機制。利用這樣的方式讓老闆不會太多。
Cluster Head 之間的相互連線問題
現在就是那個連線的問題，剛剛說任何的一個 device 都會有一個 cluster head 照顧，那 class head 到底會不為互相連在一起？所以我們的論文有去推論，當我們的 ra 跟 rv 調成 1:2 的時候，有很大的機率 head 跟 head 之間是在彼此的傳輸距離裡面，可以找到一個 path ，從一個 head 到另外一個 head 。所以距離是在 ra 跟 rv 是在 1:2 ，遠程是一，短程是二的距離。遠程用原本的 802.11 的距離， member 用一半的傳輸距離，只有 head 與 head 之間是用無線電遠程的距離， head 跟 member 之間是用一半的距離，剛剛有講耗電是距離的二到五次方，這樣就省了四倍以上的電量。光是無線電傳輸就可以省這麼多。
Cluster Head 的數量控制
這邊還有好多細節，結構上，老闆要照顧嘍囉，也要照顧其它老闆，內外都要兼顧。所以老闆要一直切來切去，一會兒 channel A ，一會兒 channel B ，一下長距離，一下短距離，一些複雜的控制細節不說了。其實我們很關心的其實在這裡，當我們選 ra:rv 1:2 的情況之下，我們發現老闆不會太多，一百個點只有三十三個 cluster head 。其實跟數量沒有關係，跟距離、密度有關係。五百個底在同樣的範圍裡，我們的 head 沒有增加很多，像一百個點是三十三，到五百個點是四十五，一千個點在五十個左右。所以我們的老闆是跟實驗範圍有關係，跟節點數沒關係。老闆不會隨著密度增加而增加，大部份的人都是非老闆。
Cluster 與 Cluster 之間的 Routing
再來我們還關心一件事就是 routing ，我們怎麼透過老闆的幫忙把封包送出去。這又有很多細節了，這邊有個例子。這邊有個幫派的男生要送信給另一個幫派的女生，羅密歐送信給朱麗葉，就先跟老闆講有封包要送，老闆先思考看是不是送到幫派裡，沒有的話就把需求往外送。張三要送給李四，第一步是要發現李四在哪裡，先請別人幫查李四在哪裡。張三先問老闆說李四在哪裡，老闆問底下的員工說有沒有李四，有的話就給他回覆了，沒有的話就問其它的老闆，有沒有人叫做李四。每個老闆收到請求的第一個動作就是，先問自己的員工有沒有是李四的，有就馬上回應，沒有的話再把請求往外廣撥。這個請求會逐漸的往外發送，先送給四個鄰居，我的四個鄰居會送給鄰居的四個鄰居，次數成長。最後終於會送到李四所在，李四要回應，就依照原本 route and request 走的路徑，回到原本 source 的地方。那之後，我的 source 就照著剛剛 reply 回來的路徑，就可以透過這個老闆、這個老闆、這個老闆、這個老闆，張三就可以把資料送到李四那邊去。這個就是一個機制的設計，這裡會比較複雜，有不同的 channel 要切來切去。時間不夠，有興趣的可以自己參考。
使用 Cluster 機制的演算法的實驗結果：設備壽命變長，生命週期資料流變多
我們發現我們的 class head racial 比例越來越少，節點數越多，當 head 的人比例當然越來越少，我們的 head 幾乎是一個常數， head 的數量是在一個模擬的範圍的關係。我們當然沒辦法做到一千點，花時間，耗精力。發現我們的存活率很高，就是我們的無線電設備可以用很久。當然我們關心的是效率高不高，都在睡覺沒有產量，或者產量不高。睡沒關係，期中考考試考好就好。我們看，不睡覺的話 throughput 非常高，很合理，不睡覺的話送資料量很大，我們睡覺的時候會低一點，也很合理。為了讓壽命長一點， throughput 就下降，單位時間傳送的資料量就會下降。不過我們反過來看， throughput 這邊我們不看瞬間的資料傳輸量，我們看設備從有電到沒電，所傳輸的資料量來一較高下。可以發現，用我們的方法，比 A 高出兩三倍，所以達到我們的目標：省比較多的電， throughput 以生命週期來看是多很多的。
結論：雙頻道、雙傳輸距離的 Cluster 有效完成預期目標，具有學術價值
結論技術使用是使用雙頻道、雙傳輸距離，為了省電，為了讓更多的節點可以容納進來， class head 不會太多， head 與 head 之間還是能聯絡的上。我們的退場機制使得 head 不會太多。大部份的網路卡都是把 mac address 做死在網路卡的網路介面，將我們的技術變成國際標準，以後要能改網路卡的 mac address 。學術上它是 pratical ，是有它的學術價值，所以你們可以考量一下。當然我們把這個工作轉到 wireless netwok ，節點比較少，網路卡的 mac address 是放在作業系統，在這個地方做 mac 其實是更可行的。當然在 wireless network 省電更重要，是用三號電池來撐，設備半天就沒電了。
問題之一：設備會一下子睡一下子醒，這樣設備剛加入一個網域會不會有衝突？
回答問題之一：我們是一進入系統就會有一個 initial 的起始狀態，會等等看有沒有其它的 host 存在，所以不會有問題。這是起始狀態，你要 reset 當你離開一個網域進入另一個時，有 head 就跟，沒有 head 就自己當 head 。
問題之二：在求 quorum 的時候，是用十字。如果要用兩個交叉的斜線？
回答問題之二：也可以，可是這樣不會更省。最省的是，一個 row 跟一半的 colume ，這樣是最省的。
問題之三：距離兩倍，那個會不會三個人之間，之間會有洞？
回答問題之三：兩倍是在 density 在無窮大的時候才可以證明， density 在不是無窮大的時候會有洞。有洞的話 member 會自己變 head 。當然太稀疏的話 head 與 head 也會沒辦法連，會變的沒效，所以這個系統比較適合用在 high density 。
後續問題：有沒有更 optimal 的演算法讓 head 數量比較小， cover 更多的 member ？
後續回應：這問題很多人在討論，這種討論就是他知道 partition ，才可以找到 optimal 。
問題之四：兩個 channel 的使用，如果其中一個 channel 的效率不好，使用率不高，那麼把兩個 channel 合成一個 channel 來用，使用 time division multi-duplex ，會不會比較有效率？
回答問題之四：其它演算法是用兩個不同的傳輸設備兩個 channel ，這邊是用一套，不同的時間使用不同的 channel 切換使用，硬體沒有增加。其實底層就是 time division 的。
|