【第8章─從螞蟻循跡和螢火蟲閃爍到無線通訊網路】

無線通訊網路遍佈於我們生活的四周。除了當今最熱門的手機行動通訊系統以及在辦公室或家中用來上網的無線區域網路之外，尚有許多無線網路的應用，例如用在環境或工廠監控的無線感測網路、用以提升生活品質的無線智慧家庭網路、以及用以連繫路上車輛的無線車載網路等。無線網路的應用日益增加，也愈來愈普及於我們的生活。在未來的世界裡，我們期待所有的無線系統都能互相聯結，構成一個大型的異質無線通訊網路，將人與機器、社群與生活環境做緊密的連結。

無線網路面面觀

在設計大型無線網路時，會面臨許多難以解決的工程問題，如演算法的可擴充性問題、系統的強健性問題、分散式管理的問題以及傳輸頻寬限制的問題。

1.可擴充性和系統強健性

所謂演算法的可擴充性，所指的就是這個演算法在大型網路中是否依然可以有效運作的特性。很多的演算法並不具有此功能，例如，當我們有三、五好友打算相約看電影時，我們可以由其中一位同學一一地打電話聯絡所有人；但是，當有三、五萬人要一起去看電影時，一個一個的打電話聯絡，似乎就不是有效率的做法。另外，一個系統是否具備強健性，端看系統是否容易因為少數電子設備的損壞或是遭受攻擊而造成系統的癱瘓。

2.分散式管理和傳輸頻寬限制

若要採取集中式的管理，網路往往需要很複雜的控制機制以及大量的溝通頻寬，在實際的無線系統下是不被允許的；然而，若要採用分散式的管理方式，亦即由每個個體或是小群體做自我管理的方法，又不容易達到系統的最佳化。因此，要設計一個能有效運行的大型無線通訊網路，是一件極具挑戰的事情。

3.自然界的大型生物群體網路

有趣的是，在自然界中其實隨處可見具有上述特性的大型生物群體網路。這些生物群體透過簡單的個體行為準則並且僅利用區域性的資訊和分散式的管理，達到複雜的群體智慧。人們熟知的例子有：螞蟻的循跡覓食行為、螢火蟲的同步閃爍行為、蜜蜂的集體築巢行為、魚的群游行為、神經細胞操控生物的感知與反應的行為等。若能將這些生物個體的運行機制移植到我們的無線裝置之中，相信其所構成的大型無線網路亦能展現驚人的群體智慧。以下，我以網路路由問題和網路同步問題為例，介紹如何透過仿效螞蟻的循跡覓食行為和螢火蟲的同步閃爍行為，得到有效解決上述問題的方法。

網路路由同步：尋找「最佳路徑」

首先，何謂路由問題？
路由問題基本上就是如何找出從甲地到乙地的最佳路徑的問題。

這樣的問題是我們平常開車上路或是出遊所會面臨的問題。同樣地，在大型無線網路中，相隔兩地的電腦若要互相溝通，其所傳送的訊息需要網路經過網路中的不同路徑，並利用中不同的路由器或是電腦的轉傳，方能將訊息從傳送端順利地送達目的端。在傳送之前，電子裝置必須先確認訊息應透過哪些裝置的轉傳，也就是應透過哪一條路徑來傳送才是最好的。所謂的最佳路徑在不同應用中有不同的定義；在網路中，這可以是傳送延遲最短的路徑、傳送頻寬最大的路徑、傳送最可靠的路徑等。若每個電子裝置上都備有無線網路的完整圖資（亦即哪些電子裝置間有連結、每條連結上的頻寬和延遲為何等），即可利用許多有效的演算法（如Dijkstra演算法或是Bellman-Ford演算法）來幫助我們計算出最佳的路徑。然而，無線網路最大的挑戰即在於無線裝置都是不時地在移動，而且通訊連結經常是不穩定的。因此網路圖資每分每秒都在改變。試想，若汽車導航系統的圖資過時，我們就會經常面臨找不到路的窘境。此時，我們即可跟廠商購買更新的圖資或是上網下載新的資訊。但是在無線網路中，並沒有一個可即時監控網路變化的中央控制台，此時，網路中的各個裝置應如何取得圖資呢？傳統上經常使用的方法，就是透過不斷地跟鄰居（亦即有直接連結的其他無線裝置）打招呼進行資訊交換，如圖8-1所示。每次跟鄰居打招呼，不僅可以讓兩人得知彼此之間的連結狀態，更可以互相告知自己已取得的圖資。藉由不斷反覆地打招呼，最終每個裝置都將能取得完整的圖資。然而，若網路過大，要取得完整的圖資相當費時，而且，在網路不斷變動的情況下，這樣的不斷更新會相當耗費頻寬資源。