Wireless sensor networks (WSNs) are the demanding application-oriented networks whose primary goals are to provide information about physical environments without human intervention. In WSNs, it is typical that a huge number of resource-constrained sensor nodes are deployed over physical environments. Therefore, auto-configuration is essential for wireless sensor networks to form a network topology by individual nodes themselves. The importance of auto-configuration is also proved in that diverse wireless personal are network standards such as IEEE 802.15.5, ZigBee, 6LoWPAN, and IETF ROLL have adopted auto-configuration function in their specification. In addition to this auto-configuration, opportunistic communications have been emerged as a solution to improve throughput of physical channels by exploiting broadcast nature of wireless medium and spatial diversity over lossy link environment of wireless sensor networks. In the opportunistic communications, packets are forwarded through competition among nodes who received broadcasted packets successfully, which is differently from traditional communication designating the next hop node, for the reliable packet delivery in vulnerable link conditions. This dissertation provides opportunistic communications composed of any-to-any multi-hop routing and multi-hop dissemination protocols based on auto-configuration of wireless sensor networks. The proposed algorithms are applied into auto-configuration phase in order to minimize bandwidth, memory, and processing cost during network operation phase considering the resource constraints of wireless sensor networks, and we also achieve efficient and reliable communication by exploiting opportunistic communications against lossy link environment of wireless sensor networks.
The proposed algorithms in this dissertation are composed of network topology formation, any-to-any multi-hop routing, and multi-hop dissemination, which are essential functions for wireless sensor networks. The network topology formation algorithm provides minimum cost tree topology, which is a basis of oppor-tunistic communications. It constructs a tree topology that minimizes sum of all pairs tree routing cost by selecting optimal parent-children relationship during auto-configuration. The any-to-any multi-hop routing protocol works on this minimum route cost tree and utilizes hierarchical address dynamically assigned during auto-configuration. It provides reliable any-to-any routing by allowing each node to forward in an opportunistic manner based on hop distance calculated with hierarchical addresses of source and destination. The multi-hop dissemination protocol utilizes broadcast schedule information dynamically assigned during auto-configuration phase, and each node rebroadcasts a packet according to this broadcast schedule and receives from several predecessors in an opportunistic way.
In summary, these algorithms are designed to obtain the necessary information during auto-configuration phase in order to minimize resource consumption during network operation phase, for example, when each node performs auto-configuration, it is assigned parent-child relationship for the minimum route cost tree, a hierarchical address structure for opportunistic anypath routing, and broadcast schedule for efficient and reliable dissemination. It also maximizes efficiency and reliability of multi-hop communications by exploiting this information and opportunistic communication mechanism for resource constrained and lossy wireless sensor networks.
네트워크 자율구성 기능은 대규모의 센서 노드를 임의로 배치하는 무선 센서 네트워크에서 필수적인 기능으로, 각 노드들은 사용자의 개입 없이 노드 간 어소시에이션 절차를 통해 네트워크 토폴로지를 구성하게 된다. 자율 구성 기능은 IEEE 802.15.5, ZigBee, 6LoWPAN, IETF ROLL 등 다양한 저속, 저전력 홈 네트워크 표준 사양에 포함되어 있으며, 각 노드들은 이웃 노드 탐색 및 어소시에이션 절차를 통해 네트워크를 구성하도록 정의되어 있다. 오퍼튜니스틱 통신 기법은 무선 센서 네트워크에서의 링크 불안정성을 고려하여 브로드캐스트 기반의 공간적 다양성을 활용하는 기법으로써, 기존 통신 방식에서 특정 노드를 지정하여 유니캐스팅하는 방법과는 달리 패킷 수신 노드 간 경쟁을 통한 브로드캐스팅 기반 전달 과정을 통하여 패킷 전송의 신뢰성을 높이는 기법이다. 본 연구에서는 무선 센서 네트워크의 자율구성 기능을 이용하여 임의 노드 간 멀티 홉 라우팅 및 브로드캐스팅을 지원하는 오퍼튜니스틱 통신 기법을 제안하며, 무선 센서 네트워크의 자원 제약을 고려하여 제안 기법들을 자율 구성 단계에서 적용함으로써 네트워크 운영 단계에서의 오버헤드를 최소한으로 줄일 뿐만 아니라, 오퍼튜니스틱 통신 기법을 이용하여 무선 링크의 불안정 환경에서도 효율적이고 신뢰성 있는 통신을 제공하도록 한다.
본 연구에서 제안하는 기법들은 무선 센서 네트워크에서 필수적인 기능이라 할 수 있는 네트워크 토폴로지 구성, 임의 노드 간 멀티 홉 라우팅, 멀티 홉 브로드캐스팅 기법으로 구성되며, 네트워크 토폴로지 구성 알고리즘에서는 오퍼튜니스틱 통신의 근간이 되는 최소 라우팅 비용 기반 DC-MRCT (Degree Constrained Minimum Route Cost Tree) 토폴로지의 구성 기법을 제안한다. 즉, 네트워크 자율 구성 단계에서 라우팅 비용을 최소로 하는 부모-자식 관계를 선택하도록 함으로써 네트워크 내 모든 경로에서의 라우팅 비용의 합을 최소로 할 수 있는 트리 토폴로지를 구성하게 된다. 임의 노드 간 멀티 홉 라우팅 기법인 OSTR (Opportunistic Shortcut Tree Routing) 프로토콜은 앞서 제안한 DC-MRCT토폴로지에서 동작하며, 자율 구성 단계에서 동적으로 할당되는 계층적 주소를 통해 계산된 목적지까지의 남은 라우팅 비용을 우선순위로 하는 브로드캐스트 기반 오퍼튜니스틱 패킷 전송 기법을 이용함으로써 링크 불안정 환경에서의 패킷 전송 신뢰성을 높인다. 멀티 홉 브로드캐스팅 프로토콜에서는 자율 구성 단계에서 동적으로 할당되는 브로드캐스트 스케쥴링에 따라 수신한 패킷을 전송하며, 링크 환경에 따라 이웃 노드들로부터 오퍼튜니스틱 방식으로 패킷을 수신하도록 함으로써 효율적이면서도 신뢰성 있는 브로드캐스팅을 제안한다.
마지막으로 본 연구에서 제안하는 기법들은 자율 구성 기능과 함께 동작하도록 설계함으로써 자원이 제약된 무선 센서 네트워크 운영 단계에서 제안 알고리즘 적용 과정에서의 채널 대역폭, 메모리 및 프로세싱의 소모를 최소화하도록 하였으며, 무선 링크의 불완전 환경을 고려하여 오퍼튜니스틱 방식의 멀티 홉 라우팅 및 브로드캐스팅 기법을 통하여 무선 패킷 전송의 효율성 및 신뢰성을 제공할 수 있도록 제안하였다. 이에 본 연구에서 제안한 네트워크 자율 구성 기반의 오퍼튜니스틱 통신 기법이 향후 연구, 개발될 다양한 무선 센서 네트워크 시스템 및 표준 프로토콜에서 활용됨으로써, 무선 센서 네트워크 시스템의 활성화에 기여할 수 있기를 기대한다.