$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

무선 네트워크에서 최소 전력 브로드캐스트를 위한 트리 기반 탐욕 알고리즘
A Tree-based Greedy Algorithm for Minimum Power Broadcast in Wireless Networks 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.21 no.5, 2017년, pp.921 - 928  

이동호 (Department of Data Information, Korea Maritime and Ocean University) ,  장길웅 (Department of Data Information, Korea Maritime and Ocean University)

초록
AI-Helper 아이콘AI-Helper

유선 네트워크와 달리 무선 네트워크 환경에서의 브로드캐스팅은 단일 전송으로 다수의 노드로 데이터를 한 번에 송신할 수 있다. 무선 네트워크에서 노드의 전방향 브로드캐스팅은 인접한 모든 노드에게 동시에 도달한다. 본 논문에서는 무선 네트워크에서 브로드캐스팅 시 전체 송신 전력을 최소화하는 최소 전력 브로드캐스팅 문제를 해결하기 위한 탐욕 알고리즘을 제안한다. 제안된 알고리즘은 각 노드의 최대 전송 범위 내에서 메시지를 전송할 수 있는 노드의 집합인 이웃 노드 리스트를 이용하여 데이터를 수신한 송신 노드 중 이웃 노드를 가장 많이 가지고 있는 노드가 우선적으로 이웃 노드로 데이터를 전송한다. 제안된 알고리즘은 컴퓨터 시뮬레이션을 이용하여 성능평가가 이루어졌으며, 네트워크상의 모든 노드로 브로드캐스팅 시 소요되는 송신 전력과 브로드캐스팅 횟수의 관점에서 기존의 알고리즘과 비교하였다. 실험 결과에서 제안된 알고리즘은 기존의 알고리즘보다 성능이 우수함을 보인다.

Abstract ▼ AI-Helper 아이콘AI-Helper

Unlike wired networks, broadcasting in wireless networks can transmit data to several nodes at a time in a single transmission. The omnidirectional broadcasting of node in wireless networks simultaneously reaches all neighboring nodes. In this paper, we propose a greedy algorithm to solve the minimu...

주제어

#무선 네트워크   #최소 전력 브로드캐스트   #최소 비용 신장 트리   #탐욕 알고리즘  

AI 본문요약
AI-Helper 아이콘 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

  • 무선 네트워크에서 브로드캐스트 성능을 향상시키기 위한 연구는 확률에 기반 한 방법, 최소 비용 신장트리(Minimum Spanning Tree: MST)를 이용한 방법, 이웃 노드 정보를 이용한 방법, 클러스터를 구성하는 방법 등으로 분류할 수 있다. 본 논문에서는 이들 중 이웃 노드 정보를 이용하여, 각 노드의 브로드캐스트 메시지 수신 상태를 고려한 탐욕 알고리즘을 제안한다. 각 노드들의 전송 반경 내에 있는 이웃 노드들을 탐색한 뒤, 가장 많은 이웃 노드를 가지고 있는 노드에게 우선적으로 브로드캐스팅을 수행하여 에너지 효율을 높이는 방법을 제안한다.
  • 본 논문은 무선 네트워크에서 최소 전력 브로드캐스팅 문제를 해결하기 위한 방법으로 트리 기반으로 한 탐욕 알고리즘을 제안하였다. 무선 브로드캐스트는 단일전송으로 여러 노드와 통신할 수 있기 때문에 본 논문에서 제안한 알고리즘은 이웃 노드 리스트를 이용하여 한 번의 전송에 최대한 많은 노드들과 통신할 수 있게 브로드캐스트 우선순위를 부여함으로써 전송 에너지 효율을 높이는 방법을 제안하였다.
  • 본 장에서는 무선 네트워크에서 MPB 문제를 해결하기 위해 트리 기반의 탐욕적인 휴리스틱 알고리즘을 제안한다. 각 노드들의 브로드캐스팅 시 묵시적 전송을 받는 노드들이 많을수록 전체 네트워크의 전송 횟수가 적어 송신 에너지를 절약할 수 있다는 가정 하에, 이웃 노드의 정보를 이용하여 가장 많은 이웃 노드를 가지고 있는 노드에게 브로드캐스트 우선순위를 부여한다.

가설 설정

  • 본 장에서는 무선 네트워크에서 MPB 문제를 해결하기 위해 트리 기반의 탐욕적인 휴리스틱 알고리즘을 제안한다. 각 노드들의 브로드캐스팅 시 묵시적 전송을 받는 노드들이 많을수록 전체 네트워크의 전송 횟수가 적어 송신 에너지를 절약할 수 있다는 가정 하에, 이웃 노드의 정보를 이용하여 가장 많은 이웃 노드를 가지고 있는 노드에게 브로드캐스트 우선순위를 부여한다.
  • 처음 브로드캐스팅을 수행하는 소스 노드와 나머지 노드는 직접 또는 호핑(hopping) 방식으로 통신하며, 각 노드들은 다른 노드에게 데이터를 전송하는 중계 노드의 역할을 수행할 수 있다. 신호 수신, 데이터 처리 동작에 관련된 에너지 소비는 없다고 가정하며, 송신 전력은 실제로 데이터를 주고받는 노드들의 유클리드 거리에 비례한다. 네트워크에 존재하는 모든 노드들에게 데이터를 송신하는 것이 목적이므로, 각 노드들은 적어도 하나 이상의 노드들과 통신할 수 있다.
본문요약 정보가 도움이 되었나요?

질의응답

핵심어 질문 논문에서 추출한 답변
네트워크에서 브로드캐스팅은 어떤 방식인가? 데이터를 전송하는 방식은 크게 유니캐스트, 브로드캐스트, 멀티캐스트 세 가지 방법으로 나눌 수 있으며, 이들 중 브로드캐스트는 라우팅 경로를 획득하기 위한 효율적인 전송 방식 중 하나이다. 네트워크에서의 브로드캐스팅은 네트워크상에 존재하는 모든 노드로 메시지를 전송하는 방식이며, 다수의 수신자에게 효율적으로 동시에 데이터를 전달하기 위해 사용된다[5]. 무선 네트워크에서 하나의 특정 노드에게 데이터를 직접 전송하는 유니캐스트 방식과는 달리, 브로드캐스트는 노드의 단일 전송만으로 주위의 여러 노드로 메시지를 보낼 수 있다[6].
데이터를 전송하는 방식의 세가지 방법은 무엇인가? 데이터를 전송하는 방식은 크게 유니캐스트, 브로드캐스트, 멀티캐스트 세 가지 방법으로 나눌 수 있으며, 이들 중 브로드캐스트는 라우팅 경로를 획득하기 위한 효율적인 전송 방식 중 하나이다. 네트워크에서의 브로드캐스팅은 네트워크상에 존재하는 모든 노드로 메시지를 전송하는 방식이며, 다수의 수신자에게 효율적으로 동시에 데이터를 전달하기 위해 사용된다[5].
무선 네트워크에서 최소 전력 브로드캐스팅 문제를 해결하기 위한 방법인 트리 기반으로 한 탐욕 알고리즘을 제안하였는데 이 기술을 사용하였을때 기대할 수 있는 효과는 무엇인가? 시뮬레이션 결과에서 소규모 네트워크 환경이나 노드의 밀도가 낮은 네트워크에서는 BIP, MST 알고리즘의 에너지 소모가 효율적이었지만 대규모 네트워크나 노드의 밀도가 높은 네트워크에서는 제안된 알고리즘의 성능이 전송 에너지와 전송 횟수 측면에서 효율적임을 알 수 있었다. 따라서 제안된 알고리즘이 무선 네트워크에서 최소 전력 브로드캐스팅 문제를 효과적으로 해결할 수 있음을 볼 수 있었다.
질의응답 정보가 도움이 되었나요?

참고문헌 (11)

  1. I. F. Akyildiz, W. Su, Sankarasubramaniam, and Y. E. Cayirci, "Wireless sensor networks: a survey," Computer networks, vol. 38, no. 4, pp. 393-422, 2002. 

    상세보기 crossref

  2. I. Caragiannis, M. Flammini, and L. Moscardelli, "An exponential improvement on the mst heuristic for minimum energy broadcasting in ad hoc wireless networks," IEEE/ACM Transactions on Networking, vol. 21, no. 4, pp. 1322-1331, Aug 2013. 

    상세보기 crossref

  3. R. Montemanni and P. Mahdabi, "A Linear Programmingbased Evolutionary Algorithm for the Minimum Power Broadcast Problem in Wireless Sensor Networks," Journal of Mathematical Modelling and Algorithms, vol. 10, pp. 145-162, June 2011. 

    상세보기 crossref

  4. K. Akkaya and M. Younis, "A survey on routing protocols for wireless sensor networks," Ad hoc networks, vol. 2, pp. 325-349, 2005. 

  5. D. Nguyen et al, "Wireless broadcast using network coding," IEEE Transactions on Vehicular technology, vol. 58, no. 2, pp. 914-925, 2009. 

    상세보기 crossref

  6. A. K. Das et al, "Minimum power broadcast trees for wireless networks: integer programming formulations," In Proceeding of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, vol. 2, 2003. 

  7. J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "Resource-limited energy-efficient wireless multicast of session traffic," In Proceeding of System Sciences, 2001. 

  8. T. K. Song, J. J. Kang, and H. S. Ahn, "A Flooding Scheme Based on Packet Reception Counts for Ad Hoc Networks," The Journal of The Institute of Internet, Broadcasting and Communication, vol. 11, no. 2, pp. 197-203, 2011. 

  9. O. K. Tonguz et al, "On the broadcast storm problem in ad hoc wireless networks," In Proceeding of International Conference on Broadband Communications, Networks and Systems, pp. 1-11, 2006. 

  10. J. Wu and F. Dai, "Broadcasting in ad hoc networks based on self-pruning," International Journal of Foundations of Computer Science, vol. 14, no. 2, pp. 201-221, 2003. 

    상세보기 crossref

  11. J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "On the construction of energy-efficient broadcast and multicast trees in wireless networks," In Proceeding of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 585-594, 2000. 

저자의 다른 논문 :

관련 콘텐츠

오픈액세스(OA) 유형

GOLD

오픈액세스 학술지에 출판된 논문

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로