서지주요정보
K-hop gossiping for radio networks = 라디오 네트워크를 위한 k-홉 가십핑
서명 / 저자 K-hop gossiping for radio networks = 라디오 네트워크를 위한 k-홉 가십핑 / Hyun-Seob Lee.
저자명 Lee, Hyun-Sseob ; 이현섭
발행사항 [대전 : 한국과학기술원, 2012].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8023466

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 12002

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Wireless multi-hop radio networks such as ad hoc or sensor networks have drawn considerable at-tention in the past few decades. And there is a growing tendency to consider large-scale networks with rapid progress in manufacturing technology of sensor nodes. Broadcasting and gossiping are two classical problems of information dissemination in communication networks. Broadcasting is the process of distribution of in-formation given to a source node to every other node of the network. Gossiping is a generalization of broad-casting where each node acts as a source node: each node shares its own message to all other nodes in the network. Fundamentally, gossiping requires heavy communications compared with broadcasting and it costs more as the size of network grows. Motivated by gossiping in the large-scale radio networks, I consider a par-tial gossiping, $k$-hop gossiping. In $k$-hop gossiping, each node shares its own message with nodes within distance $k$-hop instead of sharing with all nodes in the network. . I give theoretical lower bound and upper bound in paths, cycles, trees, grids and general graphs for k-hop gossiping problem. Also I give graph proper-ties related to this problem.

센서 네트워크와 같은 무선 라디오 네트워크는 지난 십여 년간 큰 관심을 받아왔다. 라디오 통신 장치를 탑재하는 센서들의 제작 기술 발달로 인해 점점 활용 영역이 넓어지면서 네트워크의 크기도 커지는 추세이다. 브로드캐스팅과 가십핑은 통신망에서 정보를 교환하는 고전적인 두 문제이다. 브로드캐스팅은 네트워크 상에서 한 노드에게 주어진 정보를 네트워크를 이루는 모든 노드에게 전달하는 문제이다. 가십핑은 네트워크를 구성하는 모든 노드가 각각 고유한 정보를 갖고 있을 때 이 정보들을 모든 노드에게 각각 전달하는 문제로 브로드캐스팅의 좀 더 일반적인 형태로 볼 수 있다. 근본적으로 가십핑이 브로드캐스팅에 비해 더 많은 통신 복잡도를 가지며 이는 네트워크의 크기가 커질수록 더 심해지게 된다. 본 학위 논문에서는, 라디오 네트워크에서의 k-홉 가십핑 문제를 제시한다. 가십핑은 네트워크의 모든 노드들이 서로의 메시지를 모두 공유하는 과정인 반면, k-홉 가십핑 문제는 각각의 노드들이 서로의 메시지를 k-홉 이내의 노드들과 공유하는 문제이다. 라디오 네트워크를 무향 그래프로 모델링하여, 잘 알려진 선형 그래프, 원형 그래프, 트리 그래프, 격자 그래프에서의 의미있는 하한을 제시하고 하한에 가까운 알고리즘을 제시한다. 또한 그래프의 연결성과 k-홉 가십핑 문제와의 관계를 제시한다. 이는 초대형 라디오 네트워크에서의 효율적인 정보 공유에 이론적인 결과를 제공한다.

서지기타정보

서지기타정보
청구기호 {DCS 12002
형태사항 ii, 20 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 이현섭
지도교수의 영문표기 : Sung-Yong Shin
지도교수의 한글표기 : 신성용
공동교수의 영문표기 : Kyun-Yong Chwa
공동교수의 한글표기 : 좌경룡
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 References : p. 27-29
주제 gossiping
radio networks
broadcasting
algorithm
가십핑
라디오 네트워크
브로드캐스팅
알고리즙
QR CODE qr code