무선 센서 네트워크(Wireless Sensor Networks)는 기존의 애드혹 네트워크(Ad-hoc Networks)보다 제한된 노드 자원, 배터리 의존성과 같은 제약사항을 가진다. 이러한 이유로 기존의 방법들과는 다른 형태의 에너지 효율적인 라우팅 연구가 진행되었지만 여전히 많은 문제점을 가지고 있다. 그러므로 본 논문에서는 노드의 에너지와 차수를 고려한 클러스터 기반의 백본 생성 알고리즘을 제안한다. 클러스터링과 같은 계층구조 방식은 본질적으로 데이터 집중 및 융합에 유리한 장점이 있으며, 클러스터 헤드의 관리에 의해서 일반 노드들을 조정하여 전력 소모도 낮출 수 있다. 또한 백본을 구성하는 백본노드만 라우팅 정보를 유지하여 제어트래픽과 같은 통신오버헤드를 크게 줄일 수 있으며, 깨어있는 노드의 수를 최소화할 수 있다. 그러나 백본노드들은 비백본 노드의 트래픽을 모두 처리해야 하므로 에너지 소모가 크다. 따라서 에너지레벨 또는 차수가 높은 노드를 클러스터헤드로 선정해서 강건한 백본을 형성하고, 헤드 주변 노드 간 패킷전달의 역할을 분산함으로써 전체 네트워크 라이프타임(Network Lifetime)을 증가시킬 수 있는 방안을 제안한다. 시뮬레이션 결과에서 제안 알고리즘은 기존 연구에 비해 클러스터헤드의 잔여에너지측면에서 약 10.36%, 차수측면에서 약 24.05%의 성능 향상을 보이며, 네트워크 라이프타임도 향상되었다.
무선 센서 네트워크(Wireless Sensor Networks)는 기존의 애드혹 네트워크(Ad-hoc Networks)보다 제한된 노드 자원, 배터리 의존성과 같은 제약사항을 가진다. 이러한 이유로 기존의 방법들과는 다른 형태의 에너지 효율적인 라우팅 연구가 진행되었지만 여전히 많은 문제점을 가지고 있다. 그러므로 본 논문에서는 노드의 에너지와 차수를 고려한 클러스터 기반의 백본 생성 알고리즘을 제안한다. 클러스터링과 같은 계층구조 방식은 본질적으로 데이터 집중 및 융합에 유리한 장점이 있으며, 클러스터 헤드의 관리에 의해서 일반 노드들을 조정하여 전력 소모도 낮출 수 있다. 또한 백본을 구성하는 백본노드만 라우팅 정보를 유지하여 제어트래픽과 같은 통신오버헤드를 크게 줄일 수 있으며, 깨어있는 노드의 수를 최소화할 수 있다. 그러나 백본노드들은 비백본 노드의 트래픽을 모두 처리해야 하므로 에너지 소모가 크다. 따라서 에너지레벨 또는 차수가 높은 노드를 클러스터헤드로 선정해서 강건한 백본을 형성하고, 헤드 주변 노드 간 패킷전달의 역할을 분산함으로써 전체 네트워크 라이프타임(Network Lifetime)을 증가시킬 수 있는 방안을 제안한다. 시뮬레이션 결과에서 제안 알고리즘은 기존 연구에 비해 클러스터헤드의 잔여에너지측면에서 약 10.36%, 차수측면에서 약 24.05%의 성능 향상을 보이며, 네트워크 라이프타임도 향상되었다.
Routing through a backbone, which is responsible for performing and managing multipoint communication, reduces the communication overhead and overall energy consumption in wireless sensor networks. However, the backbone nodes will need extra functionality and therefore consume more energy compared t...
Routing through a backbone, which is responsible for performing and managing multipoint communication, reduces the communication overhead and overall energy consumption in wireless sensor networks. However, the backbone nodes will need extra functionality and therefore consume more energy compared to the other nodes. The power consumption imbalance among sensor nodes may cause a network partition and failures where the transmission from some sensors to the sink node could be blocked. Hence optimal construction of the backbone is one of the pivotal problems in sensor network applications and can drastically affect the network's communication energy dissipation. In this paper a distributed algorithm is proposed to generate backbone trees through robust multi-hop clusters in wireless sensor networks. The main objective is to form a properly designed backbone through multi-hop clusters by considering energy level and degree of each node. Our improved cluster head selection method ensures that energy is consumed evenly among the nodes in the network, thereby increasing the network lifetime. Comprehensive computer simulations have indicated that the newly proposed scheme gives approximately 10.36% and 24.05% improvements in the performances related to the residual energy level and the degree of the cluster heads respectively and also prolongs the network lifetime.
Routing through a backbone, which is responsible for performing and managing multipoint communication, reduces the communication overhead and overall energy consumption in wireless sensor networks. However, the backbone nodes will need extra functionality and therefore consume more energy compared to the other nodes. The power consumption imbalance among sensor nodes may cause a network partition and failures where the transmission from some sensors to the sink node could be blocked. Hence optimal construction of the backbone is one of the pivotal problems in sensor network applications and can drastically affect the network's communication energy dissipation. In this paper a distributed algorithm is proposed to generate backbone trees through robust multi-hop clusters in wireless sensor networks. The main objective is to form a properly designed backbone through multi-hop clusters by considering energy level and degree of each node. Our improved cluster head selection method ensures that energy is consumed evenly among the nodes in the network, thereby increasing the network lifetime. Comprehensive computer simulations have indicated that the newly proposed scheme gives approximately 10.36% and 24.05% improvements in the performances related to the residual energy level and the degree of the cluster heads respectively and also prolongs the network lifetime.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
가설 설정
첫째, 센서는 배터리에 기반하여 동작하므로, 에너지 고갈은 해당 노드의 기능 상실을 의미한다. 둘째, 일반적으로 무선 센서 네트워크를 구성하는 모든 노드들은 동일한 컴퓨팅과 통신 자원을 갖는다고 가정한다. 셋째, 대부분 무선 센서 네트워크 환경에서는 노드가 움직이지 않는다고 가정한다.
둘째, 일반적으로 무선 센서 네트워크를 구성하는 모든 노드들은 동일한 컴퓨팅과 통신 자원을 갖는다고 가정한다. 셋째, 대부분 무선 센서 네트워크 환경에서는 노드가 움직이지 않는다고 가정한다.
제안 방법
이때 백본을 형성하는 노드는 일반 노드에 비해서 에너지 소모가 크므로 노드의 잔여 에너지와 차수를 고려하여 강건한 백본을 형성하여 네트워크의 라이프타임을 증가시키는 것이 중요하다. 그러므로 본 논문에서는 에너지레벨 또는 차수가 높은 노드를 클러스터헤드로 선정해서 강건한 백본을 형성하고, 헤드 주변 노드 간 패킷전달의 역할을 분산함으로써 네트워크 라이프타임을 늘린다.
기존의 MaxMin D-클러스터 알고리즘은 ID를 기반으로 클러스터를 형성하지만, 제안하는 알고리즘은 잔여에너지와 차수를 고려하여 클러스터를 형성한다. 백본에 속한 노드는 자신뿐 만 아니라 비백본 노드의 데이터전달을 대행하여 데이터 처리량이 상대적으로 많고 헤드주변 노드들은 패킷포워딩을 위해 많은 에너지를 소모하므로 백본 형성 시 적절한 인자를 고려하여 백본을 형성해야 한다.
첫째, FloodMin과정에서 자신의 초기 플러딩값과 동일한 값이 나왔다면, 그 노드는 자기 자신이 클러스터헤드라고 선언한다. 둘째, 첫 번째 법칙에 적용되지 않으면 각 노드는 플러딩 배열에서 FloodMax과정의 값들과 FloodMin과정의 값들을 비교한다. 두 과정에서 동일한 값이 나왔다면, 해당 플러딩값을 초기 값으로 가지는 노드를 자신의 클러스터헤드라고 지정한다.
그러나 멀티홉 라우팅 모델은 모든 노드들이 경로설정 과정에 참여하므로 라우팅을 위한 오버헤드와 유지비용이 크기에 백본을 활용하는 방법이 대두하였다[2]. 본 논문에서는 멀티홉 클러스터링에 기반한 백본을 형성함으로써 단지 백본노드만 라우팅 정보를 유지하여 제어 트래픽과 같은 통신오버헤드를 크게 줄이고, 깨어있는 노드의 수를 최소화한다.
FloodMin과정은 FloodMax와 동일한 방법으로 진행되지만 비교한 값 중 가장 작은 값을 선택하여 현재의 플러딩 배열값에 저장하는 것이 차이점이다. 셋째, 2D 라운드 동안 저장한 플러딩 배열값을 기반으로 클러스터헤드 선정 법칙에 따라 헤드를 선정한다. 클러스터헤드 선정 법칙은 다음 절에서 설명하도록 한다.
두 번째 법칙에도 적용되지 않는다면 세 번째 법칙을 적용한다. 셋째, FloodMax의 플러딩값 중에서 가장 큰값을 선택하고, 그것을 초기 값으로 가지는 노드를 자신의 클러스터헤드로 지정한다. 위에 언급한 3개의 법칙으로 헤드선정이 끝나면 각 노드는 자신의 클러스터헤드 ID를 이웃노드에게 알린다.
따라서 본 논문에서는 기존의 Max-Min D-클러스터 기법[3]에 잔여에너지와 차수를 고려하여 멀티홉 클러스터에 기반한 백본을 형성한다. 에너지레벨이 높은 노드를 클러스터헤드로 선정해서 강건한 백본을 형성하고, 헤드 주변에 많은 노드들을 배치하여 패킷전달의 역할을 분산함으로써 전체 네트워크 라이프타임을 증가시킬 수 있는 방안을 제시한다.
대상 데이터
500m x 500m의 네트워크 크기에 28m의 전송반경을 가진 1000개 센서노드를 임의로 배치하며, 소스노드도 임의로 선정하였다. 각 센서노드들은 초기에 2.
이론/모형
백본노드는 일찍 에너지를 소모하는데, 이는 네트워크 단절현상과 함께 전체 네트워크 라이프타임을 단축 시키거나 빈번한 재클러스터링을 불가피하게 한다. 따라서 본 논문에서는 기존의 Max-Min D-클러스터 기법[3]에 잔여에너지와 차수를 고려하여 멀티홉 클러스터에 기반한 백본을 형성한다. 에너지레벨이 높은 노드를 클러스터헤드로 선정해서 강건한 백본을 형성하고, 헤드 주변에 많은 노드들을 배치하여 패킷전달의 역할을 분산함으로써 전체 네트워크 라이프타임을 증가시킬 수 있는 방안을 제시한다.
성능/효과
노드의 색깔이 옅을수록 에너지가 낮다는 것을 의미한다. HCDD는 이벤트 생선 전ㆍ후 에너지레벨의 차이가 제안 알고리즘에 비해서 크다는 것을 확인 할 수 있다. 이는 에너지레벨이 낮은 노드들이 백본을 형성했기 때문에 다수의 이벤트 발생 시 백본노드가 거의 에너지를 소모한다는 것을 나타내며, 최악의 경우에는 네트워크 단절현상과 함께 재클러스터링을 불가피하게 한다.
첫째, 클러스터 형성 초기에 각 노드는 잔여에너지와 차수를 기반으로 자신의 초기 플러딩값을 계산하고, 각 노드는 2D 크기의 플러딩 배열을 만들어서 라운드마다 선택되는 플러딩값을 저장한다. 둘째, FloodMax와 FloodMin 과정을 각 D라운드만큼 수행하는데, FloodMax 과정에서는 라운드마다 각 노드가 한홉 이웃노드로부터 전달받은 플러딩값과 자신의 플러딩값을 비교 하여 가장 큰 값을 현재의 플러딩 배열값에 저장한다. FloodMin과정은 FloodMax와 동일한 방법으로 진행되지만 비교한 값 중 가장 작은 값을 선택하여 현재의 플러딩 배열값에 저장하는 것이 차이점이다.
제안 알고리즘(ω =0.7)은 전체노드 수에 관계없이 ID기반 (HCDD)과 차수기반의 알고리즘에 비해 백본의 평균 잔여에너지량이 높다는 것을 확인할 수 있다.
백본에 속한 노드는 자신뿐 만 아니라 비백본 노드의 데이터전달을 대행하여 데이터 처리량이 상대적으로 많고 헤드주변 노드들은 패킷포워딩을 위해 많은 에너지를 소모하므로 백본 형성 시 적절한 인자를 고려하여 백본을 형성해야 한다. 제안 알고리즘을 이용하면 에너지레벨 또는 차수가 높은 노드를 클러스터헤드로 선정해서 강건한 백본을 형성하고, 헤드 주변 노드 간 패킷포워딩의 역할을 분산함으로써 네트워크 라이프타임을 늘릴 수 있다.
후속연구
FloodMin, FloodMax과정이 끝나면 4가지 법칙에 따라서 클러스터헤드를 선정한다. 첫째, FloodMin과정에서 자신의 초기 플러딩값과 동일한 값이 나왔다면, 그 노드는 자기 자신이 클러스터헤드라고 선언한다. 둘째, 첫 번째 법칙에 적용되지 않으면 각 노드는 플러딩 배열에서 FloodMax과정의 값들과 FloodMin과정의 값들을 비교한다.
질의응답
핵심어
질문
논문에서 추출한 답변
HCDD는 효율적인 데이터전달을 위해 무엇을 생성하는가?
백본에 속하지 않는 다른 노드들은 송・수신할 데이터가 없을 경우 수면상태로 전환함으로써 전력 소모를 절감할 수 있다. 애드혹기반의 백본 생성 알고리즘인 Max-Min D-클러스터를 무선 센서 네트워크에 그대로 차용한 HCDD(Hierarchical Cluster-based Data Dissemination)[4]는 효율적인 데이터전달을 위해 D홉 클러스터를 생성한다. D홉 클러스터는 모든 노드가 클러스터헤드로부터 최대 D홉 떨어져 있고, 멀티홉 방식으로 데이터가 전달되므로 규모가 큰 센서 네트워크 환경에 효율적이다.
Max-Min D-클러스터 알고리즘이 무선네트워크 환경에서 부적합한 이유는 무엇인가?
Max-Min D-클러스터 알고리즘은 노드 ID를 이웃노드에게 플러딩하고 그 ID를 랜덤수로 활용해 각 노드들이 최대 D홉 떨어진 클러스터헤드를 선정한다. 그러나 이 알고리즘은 애드혹기반의 백본 생성 기법이기에 에너지레벨에 민감한 무선 센서 네트워크 환경에는 부적합하다. 클러스터헤드 선출 시 센서노드의 잔여에너지와 차수에 대한 고려가 없기 때문에 특정 센서노드의 에너지가 급격히 고갈되는 경우가 많다.
백본을 형성하기 위한 일반적인 방법은 무엇인가?
백본을 형성하기 위한 일반적인 방법은 전체 네트워크를 클러스터로 분리하고 클러스터헤드와 게이트웨이를 연결하여 데이터전달 경로를 만드는 것이다. 이때 백본을 형성하는 노드는 일반 노드에 비해서 에너지 소모가 크므로 노드의 잔여 에너지와 차수를 고려하여 강건한 백본을 형성하여 네트워크의 라이프타임을 증가시키는 것이 중요하다.
참고문헌 (5)
C. R. Lin and M. Gerla, “Adaptive clustering for mobile wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 15, no. 7,
X. Cheng and D.-Z Du, “Virtual Backbone-Based Routing in Multihop Ad Hoc Wireless Networks,” IEEE Transactions on Parallel and Distributed Systems, 2001.
A. D. Amis, R. Prakash, D. Huynh, and T. Vuong, “Max-Min D-Cluster Formation in Wireless Ad Hoc Networks,” IEEE INFOCOM 2000, pp. 32-41, March 2000.
C.-J. Lin, P.-L. Chou, and C.-F. Chou, “HCDD: Hierarchical Cluster-based Data Dissemination in Wireless Sensor Networks with Mobile Sink,” ACM International Conference on Wireless Communications and Mobile Computing, pp.1189-1194, 2006.
H. Zhang and J.C. Hou, “Maintaining scheme coverage and connectivity in large sensor networks,” in Proceedings of NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc wireless, and Peer-to-Peer Networks, 2004.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.