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-홉 가십핑 문제와의 관계를 제시한다. 이는 초대형 라디오 네트워크에서의 효율적인 정보 공유에 이론적인 결과를 제공한다.
