2009年10月4日

當組合數學遇上資訊科學—無線網路的原理與模型

作者/陳秋媛(任教交通大學應用數學系)

組合數學跟資訊科學有什麼關係?本文將告訴你,組合數學中的單位圓盤圖如何應用到無線網路的世界,讓通訊無阻,效率更高!

若要談到組合數學與資訊科學的關係,那就不能不談到「圖」(graph)!這裡所說的圖,可不是美術館裡掛在牆上的那種圖, 而是一種可以將現實問題模型化(modeling)的工具。就讓我們先來定義什麼是圖吧!

一個圖是由「點」和「邊」這兩類元件所構成的,點所構成的集合稱為「點集合」,邊構成的集合稱為「邊集合」。習慣上,如果G是一個圖,而且它的點集合為V,邊集合為E,我們就會記為G =(V, E)。我們可以僅僅列出點集合V和邊集合E,來表示一個圖,也可以直接把圖畫出來。趕緊來看一個例子:今有一圖G,其V ={a, b,c, d, e, f, g}, E = {(a, b)(, b, c)(, c, d),(d, e)(, b, f)(, d, g)}。請注意,E中的(a, b)表示點a和點b之間有邊,這是一個無序配對(unordered pair);其餘類推。我們可以將圖G畫成圖一A的形式;當然,你也可以畫成圖一B的形式,這兩個圖都有相同的V和E 。

有「限」的無線網路

現在就讓我們簡單地介紹無線網路吧!只要是沒有使用實體纜線的網路,都可以稱為無線網路;換句話說,網路中節點之間的訊息傳遞,並不是靠實體纜線來達成的。在第二次世界大戰時,無線網路就曾扮演著避開敵軍的防守線,將資訊送往海外的重要角色。在開發中國家,硬體設施非常缺乏,無線網路也讓這些國家不需架設很多的實體纜線,就能夠使用網際網路。當然,無線網路並非沒有缺點,它的速度比有線網路慢,安全性也比有線網路低。

在無線網路中,每一個節點都有自己的「傳輸範圍」(transmission range),凡是在某個節點傳輸範圍內的節點,都可以收到該節點的訊息。你可以將一個節點想像成一個廣播電台,只要是在其廣播範圍內的聽眾,照理說都可以收聽到廣播。

無線網路模型化

怎樣能將無線網路模型化?將無線網路模型化能帶來什麼樣的好處?快來看看!所謂模型化,是經由將一個現實生活中的問題抽象化,來對應至某一模型。這麼做的最大好處,就是能運用此模型來協助我們解決原本的問題。一個相當有名的模型化的例子,就是哥尼斯堡的七橋問題。【更詳細的內容,請參閱第478期科學月刊】

回本期目錄

沒有留言: