Design for Energy Efficient Sensor Networks by Advanced Combinatorial Optimization Technique

通过先进的组合优化技术设计节能传感器网络

• 批准号: 19710134
• 负责人: MIYAMOTO Yuichiro
• 金额: $ 1.47万
• 依托单位: Sophia University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19710134/
• 关键词: 組合せ最適化; センサーネットワーク; 計算複雑度; オペレーションズ・リサーチ; ネットワーク理論; 近似アルゴリズム; 計算困難性

センサーネットワークを背景とする,アドホック無線通信ネットワークの効率的な構築法を研究した.ネットワークの構築法にはルールベースの構築法と何らかの最適化問題としてモデル化してそれを解く方法がある.最適化問題としてのモデル化およびそれに対するヒューリスティクスは既存研究として多く存在するが,モデル化した問題の難しさを明らかにした研究は少なかった.本研究では計算複雑度の観点からネットワーク構築問題を分類し,問題を簡単に解ける場合とそうでない場合を明らかにした.

A study on the construction method of the efficiency of wireless communication network based on the background of network service. The optimization problem and the solution method of the optimization problem are discussed. The optimization problem is difficult to solve and the existing problems exist. In this study, the problem of computing complexity is classified, and the problem is solved simply.

项目成果

主双対近似解法

原始对偶近似解

• 发表时间: 2007
• 期刊: Commnications of the Operations Research Society of Japan 52
• 作者: S. IMAHORI;Y. MIYAMOTO;H. HASHIMOTO;Y. KOBAYASHI;M. SASAKI and M. YAGIURA;宮本裕一郎
• 通讯作者: 宮本裕一郎

点容量付き内向木詰込問題の計算量

具有点容量的向内树包装问题的计算复杂度

• 发表时间: 2008
• 作者: 今堀慎治;宮本裕一郎;佐々木美裕;柳浦睦憲
• 通讯作者: 柳浦睦憲

点容量付き内向木詰込問題の計算複雑度(57-62)

具有点容量的内树填充问题的计算复杂度 (57-62)

• 发表时间: 2008
• 作者: 今堀慎治;宮本裕一郎;佐々木美裕;柳浦睦憲;今堀慎治,宮本裕一郎,橋本英樹,佐々木美裕,柳浦睦憲
• 通讯作者: 今堀慎治,宮本裕一郎,橋本英樹,佐々木美裕,柳浦睦憲

最短路をものすごく速く答える方法(7)

如何极快地回答最短路径（7）

• 发表时间: 2007
• 作者: 宇野毅明,宮本裕一郎;久保幹雄
• 通讯作者: 久保幹雄

The Complexity of the Node Capacitated In-Tree Packing Problem

节点容量树内填充问题的复杂性

• DOI: 10.1002/net.20476
• 发表时间: 2012
• 期刊: Networks
• 影响因子: 2.1
• 作者: Shinji Imahori;Yuichiro Miyamoto;Hideki Hashimoto;Yusuke Kobayashi;Mihiro Sasaki;Mutsunori Yagiura
• 通讯作者: Mutsunori Yagiura