With the advances in wireless technology and embedded computing, small wireless devices will be capable of self-organizing into wireless multihop networks. Different from traditional cellular networks, wireless multihop networks enable wireless devices to act as mobile routers with multihop routing functions. Examples of wireless multihop networks include mobile ad hoc networks and wireless sensor networks. These networks support a broad range of new applications, such as emergency response systems and environment monitoring.

Power conservation is critically important in wireless multihop networks, since nodes in it rely on batteries for proper operations, such as maintaining the network connectivity and successful delivering packets. Depletion of batteries in these nodes will have a great influence on overall network performance. Moreover, to ensure adequate coverage and fault tolerance, multihop wireless networks will be comprised of a large number of nodes. A large network size eliminates the option of frequently battery replacement.

The objective of our research is to design energy efficient network protocols for wireless multihop networks. In wireless multihop networks, data transmission and reception constitute the greatest part of the energy consumption. Although much has been studied on the energy efficient hardware design and radio technology for wireless devices, it is difficult for wireless multihop networks to handle the heavy protocol stacks with large protocol overhead due to the energy constraints. Our research　especially focuses on energy efficient routing issues and node addressing issues. Such networking issues are associated with the amount of packets propagated through the networks and the packet size, leading to a substantial impact on the energy consumption of wireless nodes.

Our research includes two parts. The first part is called HBRD, an efficient route-discovery protocol for ad hoc networks with global connectivity. In this work, we investigate a new application of ad hoc network integrated with wired networks, which would expand communication bases of both ad hoc networks and wired networks. We observed that when ad hoc networks are linked to wired networks by access points, the traffic tends to be non-uniformly distributed in the sense that it is more likely to be concentrated on the access points than on other nodes. Thus, route-discovery operations between mobile nodes and access points will have a substantial impact on the consumption of energy and bandwidth of the network. However, most traditional schemes of ad hoc route-discovery focus on the pure ad hoc network with a uniform traffic pattern.

To design a route-discovery scheme particularly suited to non-uniform route connectivity in terms of low routing overhead, we propose a new route-discovery scheme called Hopcount-Based Route Discovery （HBRD）. Although there are various route-discovery schemes and optimization schemes, in essence, route-discovery schemes used in ad hoc networks are based on flooding to discover routes. When using the conventional flooding-based ad hoc route discovery, route-request packets will reach every node in the ad hoc network. Though location based routing is an efficient approach to localized route discovery and reduce routing information propagation, locating system such as GPS might not be always available in ad hoc networks. By using hopcount information, HBRD reduces the number of nodes to whom route-request packet is propagated. HBRD utilizes a set of hopcounts referring to access points to limit route-discovery to a given small region. Such hopcount information is obtained and updated from advertisements of access points. Limiting the route-discovery region results in fewer routing messages and therefore saves the energy consumption. We conduct simulation to evaluate the performances of HBRD. The simulation results show that the HBRD scheme highly reduces routing overhead while preserving high rate of successfully discovering route to the destination.

The second part of our research is called ESAA. ESAA is an energy-efficient sensor address autoconfiguration scheme for sensor network. We investigate the protocol stacks in self-organized sensor networks and observed the data transmitted in a sensor network is usually very small, the length of addresses in the packet overhead should not be ignored. Using a conventional global unique addresses will have too high an energy cost.

We develop a new address autoconfiguration scheme, Energy-efficient Sensor Address Autoconfiguration scheme （ESAA）, to automatically configure small-size addresses for sensor networks with energy-efficiency. ESAA achieves energy efficiency in three ways. First, each node attempts to select a candidate address in a sequential order instead of randomly, to reduce the address conflicts during the configuration. Second, in order to reduce the total configuration overhead, ESAA allows multiple sensor nodes to cooperate to configure their addresses, instead of each sensor configuring its address individually. Third, in ESAA, minimum address-size can be setup based on the node number in the network.

ESAA addressing system is implemented on a sensor network testbed, and energy consumption on wireless sensor nodes is measured. We also conduct simulations to evaluate the performances of address configurations in a large scale sensor network, including address conflicts, configuration overhead, etc.　The results of implementation and simulations show that the proposed addressing system is energy efficient, and has low configuration overhead and few address conflicts.

Through this dissertation, "energy efficiency" is a key word. We designed two energy-efficient protocols for wireless multihop networks. These protocols achieve energy conservation by either limiting traffic overhead, such as reducing routing overhead by localizing the route discovery based on hopcounts and reducing configuration overhead, or by reducing packet size by configuring nodes with the smallest address length.

The dissertation is organized as follows.

Chapter 1　 Introduction

Chapter 2 Energy Efficient Route Discovery for Integration of Ad Hoc Network with Wired Networks

Chapter 3 Energy Efficient Addressing in Sensor Networks

Chapter 4 Implementation of ESAA and Measurement of Energy Consumption

Chapter 5 Conclusion

Chapter 1 provides an overall introduction about this thesis. It gives the background knowledge, scope and objective, key contributions, and organization of the this thesis.

Chapter 2 describes the first part of our research, HBRD. After introducing the motivation and network model for efficient route discovery in the hybrid networks of ad hoc network and wired Networks, we describe the hopcount-based route discovery protocol （HBRD） in detail from three aspects: generation of hopcount information, exchanging of hopcount information and hopcount-based route discovery mechanisms. The evaluation results are obtained from computer simulations. The performance of HBRD is studied when the node velocity, advertisement interval of access points, and other parameters are changed. The effect of our route-discovery protocol is compared with the cases of conventional ad hoc route-discovery schemes.

Chapter 3 and chapter 4 describe the second part of our research, ESAA. We at first present the motivation for node addressing in self-organized networks. After that, the network model and assumptions are described. Then, the porposed energy efficient address autoconfiguration scheme （ESAA） is described in detail from 3 aspects: address representation for sensor networks, ESAA address autoconfiguration mechanisms and address-size setup scheme. The evaluation results are obtained from computer simulations at first. The performance of ESAA is studied when the node number, address size, network and other parameters are changed. The effect of ESAA is compared with the case of IP addressing and Duplicate Address Detection （DAD） autoconfiguration scheme.

Chapter 4 presents the implementation of ESAA to a real sensor network testbed and the experiments on energy consumption measurement. At first, we introduce the system architecture of the sensor nodes used in the testbed. Then, the implementation of our addressing system is described from 2 aspects: address representations together with node states, and address autoconfiguration operations. Energy consumption about node addresses and address configurations is measured by a real-time current measurement system. The effect of ESAA addressing system is compared with the case of IP addressing and DAD autoconfiguration scheme.

Finally, Chapter 5 summarizes the outcomes of this work. It also contains a discussion of the directions for the future research.

本論文は「Energy-Efficient Protocols in Wireless Multihop Networks（無線マルチホップネットワークにおける低消費電力プロトコルに関する研究）」と題し，全5章からなる．無線通信技術や組込みコンピューティング技術の発達に伴い，小型無線デバイスにより無線マルチホップネットワークを自己組織的に構成することが可能となっている．このようなネットワークを長時間安定して動作させるためには低消費電力技術が重要となる．消費電力や，メモリ，処理能力に制約のある無線マルチホップネットワークにおいては，従来のインターネットに使われているネットワークプロトコルを適用することは難しい。本論文では無線マルチホップネットワークにおける低消費電力ネットワークプロトコルの開発を目的として，特にルーティングプロトコル及びノードアドレッシングに着目して論じている．

第1章は序論であり，モバイルコンピューティング技術の発展，無線マルチホップネットワークの応用，無線マルチホップネットワークにおける低消費電力の重要性について触れ，本研究の背景・構成と各章の目的について述べている．

第2章では「有線・無線アドホック統合型ネットワークにおける低消費電力な経路検索手法」を提案しその有効性を評価している．アドホックネットワークが無線アクセスポイントを経由して有線ネットワークに接続されている場合，有線ネットワークのノードとも通信可能であり，その場合効率的な経路検索，特に無線ノードとアクセスポイント間の経路検索は通信トラヒック量に大きく影響する．しかし，従来のアドホックネットワークにおける経路検索手法ではフラッディングに基づいた経路検索手法を用いているため通信トラヒックに与える影響は大きい．そこで本研究では経路検索のオーバーヘッドを低減するための手法として「ホップ数に基づいた経路検索手法（HBRD）」を提案している．HBRDでは，複数のアクセスポイントからの経路広告に基づいて生成されるホップ数情報を用いて，各無線ノードにおける経路検索の範囲を局所的に抑える．これにより，経路検索メッセージ数が減少し，その結果消費電力の低減が実現できる．さらに，ホップ数情報を交換しホップ数の不正確性を補正するためのホップ数調整手法を提案し，経路検索の成功率を向上させている．計算機シミュレーションにより，HBRDが高い経路検索の成功率を保ちつつ，経路検索オーバーヘッドを低減できることが示されている．

第3章「センサネットワークにおける低消費電力ノードアドレッシング手法」では，自己組織型センサネットワークの低消費電力化に向けた新しいノードアドレッシング手法に関して検討している．センサネットワークにおけるノードの計算資源・通信資源が少ないことから，アドレス長が大きくなることの影響は無視できない．従来のIPネットワークではアドレス長が大きいことによりセンサネットワークにおけるデータに対するオーバーヘッドが大きくなる可能性がある．これに対して、本章で提案している「低消費電力センサノードのためのアドレス自動割当手法（ESAA）」では，低いアドレス衝突確率と低オーバーヘッドを実現するアドレスの自動的割当により、短いアドレスの動的な設定を行う．ESAAでは，まずアドレスの衝突確率を減らすために，各ノードがランダムではなく連続的に候補となるアドレスを選択する．また，全体的なオーバーヘッドを減らすために隣接する複数のセンサノードから候補となるアドレスを収集し、アドレス衝突を検出する．さらに，ネットワーク中のノード数に基づいて動的に最小となるアドレス長を決定する．シミュレーションにより，HBRDにおいて低い設定オーバーヘッドで十分アドレス衝突確率を低くできることが示されている．

第4章「ESAAノードアドレッシングの実装と消費電力の測定」では，実際のセンサノードに提案したアドレッシング手法を実装し，消費電力の測定を行った結果について述べている．実装したセンサノードは主にマイコン，低出力無線モジュ―ル，センサ，電源の4つのコンポーネントから構成されている．このセンサノードに提案手法を実装して、動作確認を行っている。提案手法を用いた場合とインターネットアドレスを用いた場合についてノードにおける消費電力を測定・比較し，提案手法の消費電力の低減効果を実証している．

第5章は「結論」であり，本論文の成果をまとめるとともに，無線マルチホップネットワークにおける低消費電力プロトコルに関する研究の残された課題，および今後の研究の方向性について述べている．

以上これを要するに，本論文は来るべきユビキタスネットワーク社会において用いられる無線マルチホップネットワークを構成するために必要な，低消費電力の経路検索手法とノードアドレッシング手法を提案し，実装と実測によりそれらの効果を実証し、本論文の手法が，無線マルチホップネットワークを構成するために有効であることを示したものであって，今後の無線ネットワークの研究開発の進展に貢献をするものであり、電子情報学上寄与するところ少なくない．よって本論文は博士（情報理工学）の学位請求論文として合格と認められる．