Your browser does not support JavaScript!
首頁 > 研究發展
從螞蟻循跡和螢火蟲閃爍到無線通訊網路(洪樂文老師)

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

無線網路面面觀 

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

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

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

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

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

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

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

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

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

    這樣的問題是我們平常開車上路或是出遊所會面臨的問題。同樣地,在大型無線網路中,相隔兩地的電腦若要互相溝通,其所傳送的訊息需要網路經過網路中的不同路徑,並利用中不同的路由器或是電腦的轉傳,方能將訊息從傳送端順利地送達目的端。在傳送之前,電子裝置必須先確認訊息應透過哪些裝置的轉傳,也就是應透過哪一條路徑來傳送才是最好的。

    所謂的最佳路徑在不同應用中有不同的定義;在網路中,這可以是傳送延遲最短的路徑、傳送頻寬最大的路徑、傳送最可靠的路徑等。若每個電子裝置上都備有無線網路的完整圖資(亦即哪些電子裝置間有連結、每條連結上的頻寬和延遲為何等),即可利用許多有效的演算法(如Dijkstra演算法或是Bellman-Ford演算法)來幫助我們計算出最佳的路徑。

    然而,無線網路最大的挑戰即在於無線裝置都是不時地在移動,而且通訊連結經常是不穩定的。因此網路圖資每分每秒都在改變。試想,若汽車導航系統的圖資過時,我們就會經常面臨找不到路的窘境。此時,我們即可跟廠商購買更新的圖資或是上網下載新的資訊。但是在無線網路中,並沒有一個可即時監控網路變化的中央控制台,此時,網路中的各個裝置應如何取得圖資呢?

    傳統上經常使用的方法,就是透過不斷地跟鄰居(亦即有直接連結的其他無線裝置)打招呼進行資訊交換,如圖8-1所示。每次跟鄰居打招呼,不僅可以讓兩人得知彼此之間的連結狀態,更可以互相告知自己已取得的圖資。藉由不斷反覆地打招呼,最終每個裝置都將能取得完整的圖資。然而,若網路過大,要取得完整的圖資相當費時,而且,在網路不斷變動的情況下,這樣的不斷更新會相當耗費頻寬資源。

路由演算法 

    過去幾十年,工程師們不斷研擬並提出不同的路由演算法。有的方法會定期地更新圖資,以能提供即時的圖資為目標;有的方法則在有資訊要傳遞時才做路由探索,但卻需經歷較大的時間延遲。 

    然而,有效的路由演算法在螞蟻群體中早已存在,牠們又是如何辦到的呢?若以蟻窩為出發地且以食物為目的地,螞蟻群體首先會送出一大群的螞蟻去隨機的探索路徑。這些螞蟻會採取「凡走過必留下痕跡」的方式,在走過的路徑上散發一種叫做費洛蒙的化學物質。

    這些留下的費洛蒙會吸引後來經過的螞蟻傾向於選擇同樣的路徑。費洛蒙愈強,螞蟻遵循此路徑的機率就愈高;一旦螞蟻找到食物,牠就會順著費洛蒙較強的路徑,回到蟻窩。若蟻窩和食物之間存在長短不同的路徑,其中較長的路徑,會因為費洛蒙隨時間的散去而導致較少的螞蟻選擇遵循這條路徑,也因此降低費洛蒙累積的機率。最終,所有的螞蟻就會循著較短的路徑,往返於蟻窩和食物之間,如圖8-2所示。 

    在無線網路中,我們也可以依循這樣的做法,讓傳送端裝置定期的發送探索路徑的螞蟻封包。路徑上所經過的每個裝置都會紀錄與其相鄰的每個路段的「費洛蒙」量,螞蟻封包則會依據這個量隨機的去探索路徑。螞蟻封包在到達目的端後,會循著原本走過的路徑回到出發端,並延路更新路徑上裝置所紀錄的費洛蒙量,以供後來經過的螞蟻封包一個探索路徑的依循指標。這樣的方式極具強健性,因為只要一個連結斷掉,在其他路徑上會留有最佳取代路徑的訊息。此方法亦極具適應性,可因應網路變動速度和可用的頻寬資源而調整所傳送的螞蟻封包數目。 

網路同步:避免時間差 

    如此仿生的群體智慧亦可應用於解決網路的同步問題。所謂網路同步問題就是如何將網路內所有裝置準確對時的問題。這在現代數位化的通訊系統中是非常重要的,例如,當兩個裝置都要傳送資料給同一個接收端時,我們必須讓這兩個裝置在不同的時段進行傳送,然而,若兩個裝置所採用的時間沒有事先校準,傳送的封包就有可能重疊在相同的時間,造成干擾的問題。

   又比如在家庭的防盜系統中,我們可能佈建多個無線感測器來偵測小偷的侵入、偷竊和潛逃的事件,然而,若不同的感測裝置沒有同步,其事件發生的時序將無法確認。 

    網路同步過去多半是以互相詢問時間的方式進行;例如在當今的網際網路中,我們會將網路中的電腦分成不同的層級,當一台電腦需要做時間對時時,它會發送一個封包向上層的電腦詢問時間。然而,封包的傳送延遲和偶發的阻塞往往會影響同步的準確度。假設我們以人類的時間單位來看,我們要對時時,我們就需要在當日當時,寫一封信請郵差送到政府中央去詢問時間。信件在傳送的過程中需要耗費許多時間,到了政府機關又需要處理的時間,等到我們收到政府機關回信後,早已經不是欲對時的該日該時了。 

    過去幾十年,工程師們亦花費許多心思,希望可以發展出有效的同步方式,可以精確的避免或是補償這樣的時間延遲。然而,網路同步在生物群體網路中早就能夠精準地實現。常見的例子譬如有螢火蟲的同步閃爍、心臟節律細胞的同步跳動、和人類的同步鼓掌行為。這樣的同步行為,可以由脈衝耦合震盪器的理論來解釋。

    所謂的脈衝耦合震盪器可以被視為一個整點報時的時鐘。如圖8-3所示,此時鐘在每次到達整點時,會發送出一個脈衝信號給鄰近的其他時鐘。這個脈衝信號可以是螢火蟲的亮光或是電子裝置發送的無線電波。當脈衝被鄰近裝置所接收時,會刺激這些裝置(或時鐘)的指針向前調快一步,縮短它到下次發送脈衝的時間,以減少不同裝置之間發送脈衝的時間差距,進而慢慢達到同步的效果。

    例如,當我們參與同步鼓掌的行為時,我們會因為在還未拍掌前就聽到其他人的掌聲,而傾向於加快我們鼓掌的頻率,試圖去趕上其他人的掌聲。依此機制運行,整群的脈衝耦合震盪器最終將能有效地達到同步。若將此震盪器的機制應用於無線裝置中,無線網路的同步問題亦可獲得解決。 

    此同步方式藉由網路內裝置的互相討論達到同步,並不需要一個中央的伺服器來發號施令,因此,不會有因為伺服器損壞而造成同步失敗的問題,也可輕鬆的達到分散式管理。

    藉由「網路路由」和「網路同步」這兩個例子,我們介紹了如何利用存在於生物群體中的運行機制,來解決無線通訊網路的工程問題。我們相信在經過幾億年的演化之後,這些生物群體的運行機制已經是近似最佳化,且必定具有強健性和可擴充性,方可在自然界中順利的運行。   

    然而,這些機制若欲應用於當今的系統中,仍有許多的問題待解決。例如,雖然這些方法經過演化後已經證明其在自然界的適用性,它們在無線網路的環境中是否同樣有效,是一個需要探討的問題。即使能夠將這些機制有效地移植到無線網路中,也勢必需要做各種演算法參數的調整和最佳化。況且,這些運行的機制多半只是科學家們透過其對自然界的觀察和研究所得到的「猜測」。這些猜測否正確,我們實際上難以完全確認。無論如何,做為工程師的我們,應當盡量地去發揮我們的想像力,尋找各式各樣可行的方案,一步一步地去探索自然界,也一步一步地去解決各式工程問題,以提升人類的生活。

瀏覽數  
將此文章推薦給親友
請輸入此驗證碼
Voice Play
更換驗證碼