講演抄録/キーワード |
講演名 |
2019-09-06 09:40
グラフ上の制約付きランダムウェイポイント移動モデルの特性解析 ○阪口亮太・松井大樹・中村 遼・大崎博之(関西学院大) IA2019-16 |
抄録 |
(和) |
グラフ探査は離散数学における基礎的な問題の一つであり、
計算機科学や情報ネットワーク分野においても幅広く応用されている。
グラフ上の代表的な移動モデルの一つとして、
平面上の移動モデルであるランダムウェイポイント (Random WayPoint)
移動モデルの拡張である、
制約付きランダムウェイポイント (Constrained Random WayPoint)
移動モデルが存在する。
平面上のランダムウェイポイント移動モデルは、
平面上のランダムウォークよりも、
より望ましい特性を有していることが知られている。
ランダムウォークとは異なり、
ランダムウェイポイント移動モデルは目的地を有しているため、
移動エージェントは現在地から離脱する傾向がある。
しかし、グラフ上の制約付きランダムウェイポイント移動モデルの
特性はこれまで十分に明らかにされていない。
そこで本稿では、任意のグラフ G における制約付き
ランダムウェイポイント移動モデルの主要な指標 (平均再訪間隔および
平均初回到着時間) を解析的に導出する。
さらにいくつかの数値例により、
グラフの構造や密度が制約付きランダムウェイポイント移動モデルの特性に
与える影響を調査する。 |
(英) |
Graph traversal is one of fundamental problems in discrete
mathematics since it has a broad range of applications in diverse
research areas such as computer science and information networking.
In the last decade, the characteristics of random-walk-based
mobility models have been extensively studied by many researchers
through mathematical analyses as well as computer simulations. One
of the popular mobility models on a graph is the Constrained Random
WayPoint (CRWP) mobility model, which is a natural extension of the
Random WayPoint (RWP) mobility model. It has been known that the
RWP mobility model on a continuous space has many favorable
properties (e.g., fast mixing time and wide range of positional
distribution) over random-walk-based mobility model on a continuous
space. The RWP mobility model has always specific {em goals} so
that the agent is likely to deviate from the current position. Such
deviating property of the RWP mobility model has positive impact on
many applications. However, to the best of our knowledge, the
superiority of such mobility model on a graph has not been well
understood. In this paper, we derive the two major indices of the
CRWP mobility model on a graph (i.e., the recurrence time and the
first hitting time) on an arbitrary graph $G$. Furthermore, through
several numerical examples, we investigate the effect of the
topology and density of a graph on the characteristics of the CRWP
mobility model. |
キーワード |
(和) |
グラフ上の移動モデル / 制約付きランダムウェイポイント移動モデル / ランダムウォーク / 平均再訪間隔 / 平均初回到着時間 / / / |
(英) |
Mobility Model on Graph / Constrained Random WayPoint / Random Walk / Average Recurrence Time / Average First Hitting Time / / / |
文献情報 |
信学技報, vol. 119, no. 197, IA2019-16, pp. 27-32, 2019年9月. |
資料番号 |
IA2019-16 |
発行日 |
2019-08-29 (IA) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IA2019-16 |