The Journal of Korean Institute of Communications and Information Sciences (한국통신학회논문지)

The Korean Institute of Commucations and Information Sciences (한국통신학회)
권호 표지

Power, mobility and wireless channel condition aware connected dominating set construction algorithm in the wireless ad-hoc networks

무선 에드 혹 네트워크에서 전력, 이동성 및 주변 무선 채널 상태를 고려한 연결형 Dominating Set 구성 방법

  • 조형상 (인하대학교 정보통신대학원 멀티미디어통신망연구실) ;
  • 유상조 (인하대학교 정보통신대학원 멀티미디어통신망연구실)
  • Published : 2005.05.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we propose a new power-efficient and reliable connected dominating set based routing protocol in the mobile ad hoc networks. Gateway nodes must be elected in consideration of residual energy and mobility because frequent reconstruction of connected dominating set result in transmission error for route losses. If node density is high, it results in a lot of contentions and more delays for network congestion. Therefore, in this paper, we propose a new construction method of connected dominating set that supports reliable and efficient data transmission through minimizing reconstruction of connected dominating set by delaying neighbor set advertisement message broadcast in proportion to weighted sum of residual energy, mobility, and the number of neighbor nodes. The performance of the proposed protocol is proved by simulation of various conditions.

본 논문에서는 이동 에드 혹 네트워크에서 효율적인 전력 사용 및 신뢰성 있는 데이터 전송을 보장하는 연결형 dominating set 기반의 라우팅 프로토콜을 제안하였다. 연결형 dominating set 기반의 라우팅 알고리즘에서 잦은 dominating set의 재구성은 루트 손실로 인한 전송 에러를 발생시키기 때문에, 노드의 잔여 전력량과 이동성을 고려하여 게이트웨이 노드를 선택하여야 한다. 또한 같은 지역에 노드가 집중되어 있다면 매체를 공유하는 무선네트워크의 특성상 병목으로 인한 충돌 및 지연 등을 야기 시킬 가능성이 크다. 따라서 본 논문에서는 노드의 잔여전력량 및 이동성, 이웃 노드수의 가중 가산 값에 비례하여 이웃 구성 통보 메시지 (neighbor set advertisement message)의 브로드캐스팅을 지연시키는 방법을 통해 연결형 dominating set의 재구성을 최소화 하면서도 신뢰성 있고 효율적인 데이터 전송을 보장하는 새로운 연결형 dominating set 구성 방법을 제안하고 다양한 상황에서의 실험을 통해 그 성능을 비교 평가하였다.

Keywords

References

  1. Feeney, L.M. and Nilsson, M., 'Investigating the energy consumption of a wireless network interface in an ad hoc networking environment,' Proceedings of IEEE Infocom, Anchorage AK, April, 2001
  2. IEEE, 'Wireless LAN Medium Access Control and Physical Layer specifications,' IEEE 802.11 Standard, IEEE Computer Society LAN MAN Standards Committee (August 1999)
  3. T. W. Haynes, Hedetnierni S. T., and P. J. Slater, 'Fundamentals of Domination in Graphs,' A Sireis of Monographs and Text books. Marcel Dekker, Inc., 1998
  4. J. Wu and H. Li, 'On calculating connected dominating set for efficient routing in ad hoc wireless networks,' in : Proceedings of the Third International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Seattle, WA (August 1999)
  5. J. Wu and M. Gao, 'On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks,' in Proceedings of the 30th Annual International Conference on Parallel Processing, Valencia, Spain (September 2001)
  6. Chen Benjie, Jamieson Kyle, Balakrishnan H. and Morris Robert, 'SPAN: An Energy-Efficient Coordination Algorithm of Topology Maintenance in Ad hoc Wireless Networks', ACM Wireless Networks Journal, Volume 8, Number 5, pp. 481-494, September, 2002 https://doi.org/10.1023/A:1016542229220
  7. S. Guha and S. Khuller, 'Approximation algorithms for connected dominating set,' Algorithmica, 20(4):374-387, April 1998 https://doi.org/10.1007/PL00009201
  8. Y. P. Chen and A. L. Liestman, 'Approximating Minimum Size Weakly-Connected Dominating Sets for Clustering Mobile Ad hoc Networks', MOBIHOC '02, June, 2002
  9. Y. H. Kang, Y. I. Born, 'Balancing Routing Energy Consumption in Wireless Ad-hoc Network Environments', The Journal of KICS, pp. 1671-1683, Oct, 2001