1次元固定半径ランダムグラフの連結性に対する閉じた解

• Item type: SIG Technical Reports(1)
• 公開日: 2006-05-26
• タイトル: 1次元固定半径ランダムグラフの連結性に対する閉じた解
• タイトル / 言語: en
• タイトル: Closed Form Solutions on Connectedness of One- Dimensional Fixed-Radius Random Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者名: 能代, 愛; 栗原, 正仁
• 著者名(英): AI, NOSHIRO; MASAHITO, KURIHARA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では、ランダムグラフモデルのひとつである固定半球モデル（Fixed Radius Model:FRM）G=G(n R)の連結性について解析する。このモデルは、アドホックネットワークと呼ばれる無線ネットワークと明確な関係があることから近年注目を集めている。このモデルによって定義されるランダムグラフは、何らかの分布に従ってユークリッド空間上にランダムに配置されたn個の頂点と、問いなり合う超転換の距離のある半径R以内であればその頂点間に生成される辺によって構成される。したがって、このモデルは、すべての移動端末が距離R以内にある他の端末と通信できる無線ネットワークの数理モデルとして自然に考えることができる。具体的には、固定半径モデルによって定義されるランダムグラフが連結グラフである確率に関して、一次元空間に一定数の頂点が一様分布する条件の下で、解析解を示す。同様の問題について再起的な形式によって表現された結果は、著者らによって既に示されている。本論文は、再帰的な形式によって表現された結果について閉じた解を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the connectivity of graphs defined by tho Fixed Radius Model G = G(n, R). The model has a clear relationship with state-of-the-art wireless communication networks, of ten called ad-hoc networks. In this model, each random graph is defined by n nodes placed in a Eiiclideau plane randomly according to some dist,ribution; each pair of nodes la connected by au edge if and only if the distance botween the nodes is within the common radius R. Hence the model can he naturally interpreted as a mathematical model of wireless communication networks in which every mobile node can communicate with other nodes within the distance R. In this paper, we present some analytical results concerning the probability that such random graphs are connected, assuming that the fixed number of nodes are distributed in one dimensional apace according to the uniform distribution. Related results have been obtained in our previous paper only implicitly in the fonn of recursive equations. On the other hand, the results of this paper are significant. in that they are closed form solutions of the recursive equations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 2006, 号 56(2006-MPS-059), p. 73-76, 発行日 2006-05-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会