| English | | | UGC | RGC
 
主題研究起動 影響無遠弗屆
   
任人唯賢原則的歷史傳承─北京大學學生社會來源研究,1949─1999
   
媒介全球化 對中國傳媒與電訊業之影響
   
中文失讀症的腦功能圖譜
   
隨機幾何圖形及應用
   
肯亞裂谷歐羅結撒依立耶層組的古環境意義
   
用於珠三角城市群空氣污染模擬的協同虛擬地理環境系統
   
   

 



無線感測器網路由許多計算和通訊能力非常有限的感測器組成(其示意圖見圖表1)。在無線感測器網路的實際應用中,通常需要大量的感測器,加上部署環境的制約,隨機部署往往是唯一可行的選擇。在這些隨機部署的無線感測器網路中,感測器構成平面上有限的隨機點序列,它們的分佈一般假設為均勻分佈或者泊松分佈。對這些隨機部署的無線感測器網路的研究通常將網路表示為各種由隨機點序列組成的隨機平面幾何圖。隨機平面幾何圖的研究有著眾人皆知的挑戰性,其困難主要在於圖邊的局部非獨立性和非常複雜的邊界效應。在本項目研究中,我們完成了對以下三個具體問題的概率幾何研究。 

Greedy Forward Routing 的臨界通訊半徑:Greedy forwarding routing是一個簡單的局部地理路由方法,當每一個節點收到一個資料包時,它檢查在其通訊半徑內有沒有其他節點更接近 於該資料包的終點。如果沒有,就將該資料包丟棄;否則,就將該資料包傳輸給在其通訊半徑內最接近該資料包終點的節點。顯然,Greedy forwarding routing的成功與否依賴於節點的通訊半徑。最小的確保Greedy forwarding routing成功的通訊半徑定義為Greedy forwarding routing的臨界通訊半徑。Greedy Forward Routing的臨界通訊半徑的漸近概率分佈問題是資訊理論堣@個著名難題。對該問題的研究至少可以追溯到1984年,該問題25年來一直懸而未決。最近幾年,我們對該難題從事了一系列的研究,終於在今年徹底解決了該難題。

幾何鄰近圖的最大邊長: 相對鄰居圖和Gabriel圖是兩個在無線感測器網路的局部拓撲控制和地理路由中有著廣泛應用的幾何鄰近圖。它們的應用要求感測器的通訊半徑不低於它們的最大邊長。在該項目研究中,我們成功給出並證明了它們最大邊長的精確漸近概率分佈。


 
 
圖表1:無線感測器網路示意圖
圖源:http://www.dei.unipd.it/~schenato/pics/SensorNet
work.jpg

掃描統計及其應用:給定一個無線感測器網路和一個掃描集,它們的最大(最小)掃描統計定義為任意一個給定掃描集的拷貝中包含的感測器的數量的最大(最小)值。掃描統計是一個非常有用的分析工具。在該專案研究中,我們首先給出並證明了掃描統計的漸近概率分佈,然後利用掃描統計獲得了一些關鍵網路參數的幾乎確定的漸近界限。這些參數包括最大鄰居數目,最小鄰居數目,最大團數,和染色數。

以上研究成果有助於我們充分瞭解隨機部署的大規模無線感測器網路的機理。它們在其他領域包括流行病學、天文學、地質學也有著重要應用。我們解決以上問題的方法和技巧也有助於對其他問題的概率幾何研究。

儲楓教授
電腦科學系
香港城市大學
[email protected]

 
 

回頁頂