Random Interval Graph Models and Closed Form Solutions for Connectivity of One-dimensional Ad-Hoc Networks

IPSJ Web Site 15 References

Bibliographic Information

Other Title
  • ランダム区間グラフによる1 次元アドホックネットワークの連結性のモデル化とその閉じた解
  • ランダム クカン グラフ ニ ヨル 1ジゲン アドホック ネットワーク ノ レンケツセイ ノ モデルカ ト ソノ トジタ カイ

Search this article

Description

本論文では，ランダム区間グラフ（Random Interval Graph: RIG）が連結グラフである確率を解析する．このモデルは，2 次元のランダムグラフモデルの1 つである固定半径モデル（単位円板グラフ，ランダム幾何グラフともいう）を1 次元に縮退したモデルである．これらのランダムグラフは，何らかの確率分布に従ってユークリッド空間上にランダムに配置されたn 個の頂点と，互いの距離がR 以内である2 頂点間に生成される辺によって構成される．このモデルは，すべての移動端末が距離R 以内にある他の端末と通信できるアドホックネットワークの自然な数理モデルと考えられている．RIG の連結性に対する結果は，長い道路や河川，ベルトコンベアや陳列棚などの1 次元空間として近似できる領域におけるアドホックネットワークの設計に対して有益である．1 次元の有限空間内に一定数の頂点が一様分布する条件の下で，区間の両端に必ず頂点が存在するモデル（固定端RIG）とそうでないモデル（自由端RIG）の2 つのモデルについて，再帰的な積分方程式に基づく陰的な解は，著者らによってすでに示されている．本論文では，固定端RIG についてラプラス変換を利用して積分方程式の閉じた解を陽に求める．また，自由端RIG を含む5 つの派生モデルを導入し，固定端RIG の結果を利用してそれらの解析解を示す．特に，ここで示した2 つの「中継端モデル」とその解は，アドホックネットワークへの応用において現実的な意義を持っている．

We present models and analytical solutions for connectivity of one-dimensional ad-hoc communication networks. The models are based on the random interval graph (RIG), which is the one-dimensional degenerate model of the fixed radius model (also called the unit disk graph or random geometric graph). In the RIG model, a random interval graph consists of a set of the fixed number of nodes placed randomly in a one-dimensional interval according to the uniform probability distribution; each pair of nodes is connected by an edge if and only if the distance between the nodes is within the common distance R (called the radius in non-degenerate cases). The model can be naturally interpreted as a mathematical model of wireless communication networks (called ad-hoc networks) in which every mobile node can communicate with other nodes within the distance R. In this paper, we present analytical results for the probability that the RIGs are connected (i.e., there is a path between every pair of nodes). Related results have been obtained in our previous paper only implicitly in the form of recurrence formula, but the results in this paper are explicit, closed-form solutions to the recursive equations obtained by Laplace transform calculations. Actually, we consider six types of different models: the main model (fixed-end RIG) in which two additional nodes are fixed on both end points of the interval; and five derived models including the free-end RIG (which is usually just called ‘RIG’ in the literature). In particular, the results for the two models in which the interval is divided into sub-intervals by relay nodes are practically useful in the design of ad-hoc networks.

Journal

References(15)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top