無線ネットワークモデル上の省電力アルゴリズムの研究

无线网络模型节能算法研究

• 批准号: 12780213
• 负责人: 中野 浩嗣
• 金额: $ 1.34万
• 依托单位: Japan Advanced Institute of Science and Technology (2001)Nagoya Institute of Technology (2000)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12780213/
• 关键词: 無線ネットワーク; アドホックネットワーク; モーバイルコンピューティング; 確率アルゴリズム; 省電力プロトコル; ラウティング; 初期化; リーダ選択

無線ネットワーク上で、さまざまな省電力を目指した基本通信アルゴリズムの開発を行った。また、計算機シミュレーションにより、厳密な性能の解析を行った。例えば、次のような成果を得た。1.複数のIDを持たないステーションがn台ネットワーク上に存在する状況を考える。ステーションはIDだけでなく、台数nも知らない。この場合、各ステーションが勝手に送信すると、電波の混信のため、正しい通信が行えない。そこで、通信を行いたいステーションの中から、1台を選ぶ必要がある。これはリーダ選択と呼ばれる。本研究では、n台のステーションからリーダを確率1-1/fで選ぶO(loglog n+log f)時間のアルゴリズムを示した。これは、従来のO(loglog n+√f)時間のアルゴリズムに比べて大幅な改善である。また、シミュレーションでは、従来のアルゴリズムは、最悪1600ステップ動作する場合があったが、本研究のアルゴリズムは、高々60ステップであった。2.同様の状況において、全ステーションに1からnの通し番号を与えるアルゴリズムを開発した。このアルゴリズムは、高い確率で、O(n)時間で終了する。また、各ステーションは、高々O(loglog n)回しか送受信を行わない。送受信が最も電力を消費するので、それを最小化した本アルゴリズムは、省電力であるといえる。これら以外にも、無線ネットワーク上のさまざまなアルゴリズムを提案し、シミュレーションによる性能評価を行った。

The development of wireless communication systems is expected to save power. The analysis of the performance of the computer system For example, the second time, the results were obtained. 1. The number of ID's in the list is not equal to the number of ID's. The number of stations in the station is unknown. In this case, each mode of communication is successful in sending messages, mixing signals and positive communication. In the middle of the communication, there is a need to select one station. This is the first time I've ever been to a school. In this study, the accuracy rate of the change in time was 1-1/f, and the change in time was O(log n+log f). O(loglog n+ f) time is greatly improved compared with O(loglog n+ f) time. In this study, the number of cases in which a patient has been diagnosed as a disease is estimated to be 1600. 2. In the same situation, the whole system is open to the public. O(n) time is O(n). O(loglog n) returns the message to the receiver. To minimize the cost of transmitting and receiving electricity and to save electricity The performance evaluation of this project is carried out in the following ways:

项目成果

J.L.Bordim, J.Cui, T.Hayashi, K.Nakano, S.Olariu: "Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks"IEICE Trans. Fundamentals. Vol.11 No.8. 838-850 (2000)

J.L.Bordim、J.Cui、T.Hayashi、K.Nakano、S.Olariu：“Ad-hoc 无线电网络的节能初始化协议”IEICE Trans。

J.L.Bordim, J.Cui, N.Ishii, K.Nakano: "Doubly-logarithmic energy-efficient initializaiton protocol for single-hop radio netwrok"IEICE Trans. on Fundamentals. Vol.E-85A No.5(採録予定). (2002)

J.L.Bordim、J.Cui、N.Ishii、K.Nakano：“单跳无线电网络的双对数节能初始化协议”IEICE Trans on Fundamentals。 （2002）

K.Nakano, S.Olariu, A.Y.Zomaya: "-Efficient Deterministic Routing Protocols in Radio Networks"IEEE Trans. on Parallel and Distributed Systems. Vol.12 No.6. 544-557 (2001)

K.Nakano、S.Olariu、A.Y.Zomaya：“无线电网络中的高效确定性路由协议”IEEE Trans。

K.Nakano,and S.Olariu: "Energy-Efficient Initialization Protocols for Single-Hop Radio Networks with no Collision Detection"IEEE Trans.on Parallel and Distributed Systems. Vol.11,No.7. 851-863 (2000)

K.Nakano 和 S.Olariu：“无冲突检测的单跳无线电网络的节能初始化协议”IEEE Trans.on 并行和分布式系统。

K.Nakano,and S.Olariu: "Randomized Leader Election Protocols in Radio Networks with no Collision Detection"Proc.of International Symposium on Algorithms and Computation. 362-373 (2000)

K.Nakano 和 S.Olariu：“无冲突检测的无线电网络中的随机领导者选举协议”国际算法与计算研讨会论文集。