A multi-hop wireless network consists of wireless nodes that have a capability of construction a network for themselves. Since, this network does not require any fixed infrastructure, and can be reconfigured when the network topology is changed, it is studied for military applications firstly. However, commercial interest in this network has been rapidly growing because it was shown that multi-hop routing can improve network performance significantly. As a consequence, the applications areas are expanding to data networks, home networks, device networks, sensor networks, and distributed control systems. In this network, reducing energy consumption is important since many wireless nodes may be powered by batteries with limited energy. Enhancing energy efficiency of a wireless node involves all networking layers, ranging from the physical layer to the application layer. However, in this dissertation, we focus on the network layer and cross-layer design between the network layer and the Medium Access Control(MAC)layer for improve energy efficiency.
Until now, many methods for reducing energy consumption in multi-hop wireless networks are proposed in the literature. But, there is few works about routing algorithms with explicit delay constraint and cross-layer optimization between the MAC layer and the network layer. Also, previous works do not consider the upper bound of the performance of the routing protocols mathematically, and the multi-rate capability of the physical (PHY) layer protocols. To solve the problems, we study and propose minimum energy routing algorithms for multi-hop wireless networks in this dissertation. We consider three different network environments.
First, we propose a new routing algorithm for delay-constrained service in power-controlled multi-hop wireless access networks, on the assumption that the end-to-end packet transmission delay is proportional to the number of hops of a path. The proposed scheme does not require any modification of the MAC layer and outperforms Ad hoc On-demand Distance Vector (AODV) routing with respect to the average total consumed power and the average consumed power per node, while maintaining a similar average success rate. Moreover, the proposed scheme can support delay-sensitive traffic more efficiently than can AODV, and approximates the optimal solution by adjusting its parameters.
Second, we state the necessity of cross-layer design for power-efficient routing in power-controlled multi-hop wireless networks, and propose new MAC and network layer algorithms. By using interactions between layers, the proposed scheme can approximate the optimal solution. Computer simulations show that our proposed scheme, Timer-based MAC+MCPR (Minimum Consumed Power Routing), outperforms CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)+AODV and CSMA/CA+MCPR with respect to the average total consumed power and the average consumed power per node, while maintaining a similar average success rate. Moreover, it is scalable, since each node operates in a distributed manner. Although we use a metric, minimizing consumed energy per packet, our proposed scheme can be used for the power-avare routing that used minimizing cost per packet as its metric by changing only the definition of the cost.
Finally, we propose a Bandwidth-aware Minimum Energy Routing (BMER) algorithm for minimizing the required energy to transmit a packet from a source to a destination node in multi-rate multi-hop wireless networks that have no power control capability. By combining the proposed routing algorithm with the abovementioned Timer-based MAC, we can optimize the proposed BMER algorithm. The proposed scheme, Timer-based MAC+BMER, outperforms CSMA/CA+AODV and CSMA/CA+BMER with respect to the average total consumed energy/packet and the average consumed energy/packet/node, while maintaining a similar average success rate. The proposed scheme also performs at a level similar to the optimal solution, and has scalability because it requires no centralized node. Additionally, we confirm the proposed routing algorithm, BMER, is superior to AODV even when the MAC layer uses pure CSMA/CA for broadcasting RREQ packets.
멀티홉 무선 네트워크는 스스로 네트워크를 형성할 수 있는 무선 노드들로 구성된다. 이 네트워크는 고정된 인프라를 필요로 하지 않으며 일부 노드가 동작하지 않더라도 통신을 위한 경로 설정을 다시 할 수 있기 때문에 처음에는 군사적인 용도로 연구가 시작되었다. 그러나 멀티홉 전송이 시스템이 성능을 개선할 수 있다는 연구 결과들이 나오면서 데이터 네트워크, 홈 네트워크, 디바이스 네트워크, 센서 네트워크 및 분산 제어 시스템 등으로 응용 영역이 확장되고 있다. 이러한 네트워크는 수명이 제한된 배터리에 의해 구동되는 노드로 구성되기 때문에, 전체 네트워크에서 소모되는 에너지를 최소화하는 방법에 대한 연구가 필수적이다. 이러한 연구는 물리계층부터 응용계층까지의 각 프로토콜 계층에서 모두 이루어질 수 있으나, 이 논문에서는 네트워크 계층에 대한 연구 및 네트워크 계층과 매체 접근 제어(MAC)계층의 통합 계층 프로토콜 설계에 대한 연구만을 수행한다.
지금까지 에너지 효율적인 라우팅 알고리즘에 대한 많은 연구가 있었으나, 명확한 지연 제한을 갖는 라우팅 알고리즘이나 MAC 계층과 네트워크 계층의 통합 계층 프로토콜 설계에 대한 연구가 미흡하였다. 또한 수학적으로 라우팅 알고리즘의 성능 한계에 대한 연구가 부족하였고, 물리 계층에서 멀티 레이트를 지원하는 환경에서 에너지 효율적인 라우팅 알고리즘에 대한 연구가 많이 이루어지지 않았다. 이러한 문제들을 해결하기 위해 이 논문에서는 멀티홉 무선 네트워크에서의 최소 에너지 라우팅 알고리즘에 대한 연구 결과를 제시하였으며, 이를 위해 서로 다른 세 가지 네트워크 환경을 고려하였다.
첫 번째로, 전력 제어가 가능한 멀티홉 무선 엑세스 네트워크에서 제한된 지연 서비스를 위한 온-디맨드 방식의 전력을 효율적으로 사용하는 라우팅 알고리즘을 제안하였다. 이 때 단대단 패킷 전송 지연은 경로의 홉 수에 비례한다고 가정하였다. 이러한 네트워크에서는 음성과 비디오 트래픽과 같은 지연에 민감한 트래픽의 지원이 필요할 것으로 예상되기 때문에, 명확한 지연 시간 제한을 만족하며 가장 전력을 효율적으로 사용하는 경로를 선택하는 것이 현실적이다. 제안한 방식은 제한된 지연 시간 조건을 만족시키는 이용 가능한 경로들 중에 가장 전력을 효율적으로 사용하는 경로를 찾을 수 있다. 또한 네트워크에서의 전체 소모 전력과 각 노드 당 소모하는 전력 측면에서 기존의 AODV (Ad hoc On-demand Distance Vector) 에 비해 낮은 전력 소모를 보이면서, 동일한 경로 설정의 성공 확률을 보인다. 제안된 알고리즘은 MAC 계층에 독립적으로 동작할 수 있으며, 관련 파라미터를 조절함으로써 정수계획법에 의해 구한 최적해와 비슷한 성능을 보임을 확인하였다.
두 번째로, 전력 제어가 가능한 멀티홉 무선 네트워크에서의 전력을 효율적으로 사용하는 통합 계층 프로토콜 설계의 필요성을 언급하고, 네트워크 전체에서 소모하는 전력을 최소화하기 위한 새로운 통합 계층 설계 방안을 제안하였다. 본 연구에서는 기존의 연구와는 달리 전력을 효율적으로 사용하는 라우팅 알고리즘 뿐 만 아니라, 라우팅 알고리즘의 성능 최적화를 위해 적합한 MAC 계층 알고리즘도 고려하였다. 제안한 방식인 Timer-based MAC+MCPR은 네트워크에서의 전체 소모 전력과 각 노드 당 소모하는 전력 측면에서 기존의 CSMA/CA+AODV와 CSMA/CA+MCPR에 비해 낮은 전력 소모를 필요로 하면서, 비슷한 경로 설정의 성공 확률을 보인다. 더구나, 제안한 방식은 정수계획법에 의해 구한 최적해와 비슷한 성능을 보이며 분산된 구현이 가능하다. 본 연구에서는 패킷당 소모 에너지의 최소화에 중점을 두었으나 제안한 방식은 비용의 정의만 바꿈으로써 패킷당 비용의 최소화를 매트릭으로 사용하는 모든 라우팅 프로토콜에 사용할 수 있다.
마지막으로, 전력 제어 기능을 지원하지 않고 멀티레이트를 지원하는 멀티홉 무선 네트워크에서 소스 노드와 목적지 노드 사이에서 하나의 패킷을 전송하기 위해 필요한 에너지를 최소화하기 위한 대역폭인지 최소 에너지 라우팅 알고리즘 (BMER) 을 제안하였다. 본 연구에서는 각 노드가 채널 상태와 전송을 원하는 수신단과의 거리에 따라, IEEE 802.11b 표준에 따르는 서로 다른 코딩율과 변조 방식을 이용하여 전송율을 변경할 수 있다고 가정하였다. 데이터 패킷을 전송하는데 필요한 에너지를 최소화하기 위해, BMER 알고리즘에 타이머를 기반으로 한 방송 방식을 적용하였으며, 각 링크의 최대 가용 대역폭과 각 링크에서의 패킷 충돌에 의해 일어나는 재전송의 수를 고려하였다. 제안한 방식인 Timer-based MAC+BMER는 네트워크에서의 전체 소모 에너지와 각 노드 당 소모하는 에너지 측면에서 기존의 CSMA/CA+AODV와 CSMA/CA+BMER에 비해 낮은 에너지 소모를 필요로 하면서, 비슷한 경로 설정의 성공 확률을 보인다. 또한 제안된 방식은 정수계획법에 의해 구한 최적해와 비슷한 성능을 보이며 Timer-based MAC+MCPR과 같이 분산된 구현이 가능하다.
