無線隨意感測網路中的連通性與可傳遞性

Abstract

建置無線隨意及感測網路因不需要基礎的通信設施，因此可以方便地以低成本來佈建以完成不同的任務。然而沒有了基礎的通信設施，網路的連通性便成為一個重要的議題。孤立節點的個數可以當作網路連通性的評估指標。在大型無線隨意網路中，失效的節點及連線會影響網路連通性。我們透過研究孤立節點的個數及其分佈，來探討在不可靠節點與連線環境下的網路連通性。 更進一步地，在過去的研究中，通常是以圓盤模型來估測孤立節點的個數，而非以真實的通道模型來估測。但圓盤模型是假設在網路中所有節點的傳輸半徑均相同，兩個節點只要在傳輸半徑內，彼此就是連通的；因此它是一個過度簡化的通道模型。我們提出一個通用的機率通道模型，它是基於以兩個節點的連通機率為兩者距離遞減的函數，只要改變模型中的函數及兩個設定參數，就可以對應到常用的模型，如對數距離路徑損耗模型、白努利連結模型、高斯白雜訊模型、瑞雷衰減模型及中上衰減模型等。在此通用機率通道模型下，我們進而推導出可估測出網路中孤立節點數期望值的方程式，最後我們證明孤立節點個數的分佈為卜瓦松分佈。利用推導出來的方程式，我們可藉由改變網路的節點密度或是節點的傳輸半徑來調整網路的平均孤立節點個數以達到所需要的連通程度，提供網路設計者在實務上更為準確的建置依據。 在無線隨意及感測網路中，可傳遞性也是一個重要的議題。相互鄰近圖被廣泛用來研究網路的拓樸控制，例如可當作網路的虛擬骨幹來計算與維護路徑。假設每個節點有相同的傳輸半徑，如果設定傳輸半徑為不小於相互鄰近圖的最大邊長，便可以僅用鄰居的資訊來建立相互鄰近圖。我們研究要形成相互鄰近圖的最大邊長範圍與傳輸半徑的設定範圍，進而我們也推導出相互鄰近圖中超過一定長度邊長的漸近期望邊長數。 格狀繞徑法用於無線隨意及感測網路是以地理資訊為基礎的協定。在格狀繞徑法中，平面被分割成相同大小的正方形網格，兩個網格有共同的邊就稱為相鄰網格；兩個節點若位於相鄰網格且在彼此的傳輸範圍之內則被稱為相鄰節點。資料傳輸中除了最後一次的跳躍外，封包每次會被送至一個較目前更為接近目的地節點的網格。要設計一個貪婪式的跳躍策略，最大的困難與挑戰在於如何克服跳躍至局部最小點而停止封包的傳送。我們研究與設定格狀繞徑法中兩個重要的參數，網格大小與傳輸半徑，來保證封包的可傳遞性。 除了理論的研究之外，我們利用慣性感測元件實作了兩個在定位方面的應用。第一個應用稱作「加速度計星群」，這是一個新的物體移動軌跡追蹤系統，只需要使用多顆加速度計來做物體的追蹤，並不需昂貴的陀螺儀或磁力計來做角度的測量。加速度計星群是一種鬆散耦合但有固定幾何拓樸的加速度計系統。最少只需要三顆加速度計就可以做運動追蹤與方向測量。此系統易於安裝，無需複雜的校準，只要知道加速度計彼此間的距離資訊即可。它可用在輔助導航、車禍分析以及老人的照護。第二個應用為「個人導航系統」。GPS是用來做車輛導航定位的通用方法，但單機式的GPS僅能提供絕對位置資訊，其精度尚不足以應付個人導航的服務，尤其是在室內。相對的，慣性感測元件可提供高精度相對位置的三軸資訊，可用來追蹤物體。我們使用卡爾曼濾波器來整合GPS和慣性感測元件，設計了一個手持式個人導航系統。它可計算使用者的室外和室內定位與走向資訊。

Due to no need for fixed infrastructures, wireless ad hoc networks can be flexibly deployed with low cost for various missions. However, without the help of infrastructures, connectivity is a major concern. The nonexistence of isolated nodes is a prerequisite of connectivity. Nodes are called isolated if they do not have links to other nodes. In a realistic system, nodes may become inactive due to internal breakdown or being in the sleeping state, and links may be down due to harsh environment or barriers between nodes. The inactive nodes and down links cannot take part in routing/relaying and thus may affect the connectivity. We study the connectivity of wireless ad hoc networks that are composed of unreliable nodes and links by investigating the distribution of the number of isolated nodes. Furthermore, many theoretical studies on network connectivity were based on disk graph model. The disk graph model sometimes is criticized for simplifying wireless channels too much to depict the behaviors of wireless networks. Most previous analytic works were not based on practical channel models. We study this problem using a generic probabilistic channel model that can capture the behaviors of the most widely used channel models. We derive the expected number of isolated nodes and further prove that their distribution asymptotically follows a Poisson distribution. Deliverability is also a fundamental requirement in wireless ad hoc and sensor works. Without fixed infrastructures, virtual backbones are constructed and maintained for routing packets to deliver more efficiently. Relative neighborhood graphs (RNGs) are widely used to construct planar virtual backbones. However, most previous works assumed underlying networks are connected, or implicitly assumed the transmission radius can be arbitrarily increased if necessary. In addition, in order to locally construct virtual backbones, only part of structures will be constructed. This could increase the dilation factor and cause more energy consumption. By investigating the largest RNG edge length, we show that complete RNGs can be locally constructed with high probability by using only 1-hop information if the transmission radius is properly set. In grid routing, the plane is tessellated into equal-sized square cells. If communication parties are in the same cell, packets can be transmitted directly; otherwise, packets are forwarded to routing neighbors that are in cells closer to destination cells. As a greedy strategy, grid routing suffers the existence of local minima at which no neighbor nodes exist for relaying packets. To guarantee deliverability, we investigate two vital parameters of grid routing, called the grid size and the transmission radius. We shall eliminate the probability of existence of local minima by simply setting a proper grid size and a proper transmission radius. In addition to theoretical analysis, we study applications using inertial sensors. Inertial measurement units (IMUs) are widely used in various applications. We focus on the applications in positioning and navigation. We propose two applications using inertial sensors. The first application is a motion tracking system, called g-sensor constellations, in which only g-sensors but no direction sensors are used. The second is a personal navigation system for handheld devices, which is an integration of a pedestrian tracking system for handheld devices and GPS. It provides the position information with high precision.