본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

기하학적 NP-hard 문제에 대한 근사 접근법
An Approximation Scheme For A Geometrical NP-Hard Problem

김준모    (단국대학교 전자컴퓨터공학부  );
  • 초록

    센서네트워크 중에는 센서노드들이 넓은 지역에 걸쳐 정해진 위치에 산재되어야 하는 경우가 있다. 이런 경우 센서노드들을 interconnect하기 위한 최소개수의 연결노드들을 추가하는 문제가 대두되며, 이는 The Minimum number of Steiner Points라는 추상화된 문제로 귀결된다. 이 문제는 NP-hard 문제이므로, 본 논문에서는 문제가 내포하는 기하학적인 성질을 이용하여 연결노드의 최소개수에 근접하는 방안을 제시한다. 센서네트워크에서 노드의 개수를 줄임으로써 네트워크 내부에서 오가는 메시지의 교환량이 대폭 감소하게 된다.


    In some wireless sensor networks, the sensor nodes are required to be located sparsely at designated positions over a wide area, introducing the problem of adding minimum number of relay nodes to interconnect the sensor nodes. The problem finds its form in literature: the Minimum number of Steiner Points. Since it is known to be NP-hard, this paper proposes an approximation scheme to estimate the minimum number of relay nodes through the properties of the abstract from. Reducing the number of nodes in a sensor network, the amount of data exchange over the net will be far decreased.


  • 주제어

    Sensor networks .   interconnection .   deployment .   optimizations.  

  • 참고문헌 (7)

    1. S. Arora, 'Polynomial-time approximation schemes for Euclidean TSP and other geometric problems,' Proc. 37th IEEE Symp. on Foundations of Computer Science, pp.2-12, 1996 
    2. D. Chen, D.-Z. Du, X.-D. Hu, G.-H. Lin, L. Wang and G. Xue, 'Approximations for Steiner trees with minimum number of Steiner points,' Theoretical Computer Science, vol.262, pp.83-99, 2001 
    3. http://enl.usc.edu/~ningxu/papers/survey.pdf 
    4. S. Meguerdichian, F. Koushanfar, M. Potkonjak and M. B. Srivastava, 'Coverage Problems in Wireless Ad-hoc Sensor Networks,' Proc. IEEE INFOCOM, vol.3, pp.22-26, 2001 
    5. S. S. Dhillon and K. Chakrabarty, 'Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks,' Proc. IEEE Wireless Communications and Networking Conference, pp.1609-1614, 2003 
    6. F. K. Hwang, D. S. Richards and P. Winter, 'The Steiner Tree Problem,' Annals of Discrete Mathematics, North-Holland, vol.53, 1992 
    7. G.-H. Lin and G.L. Xue, 'Steiner tree problem with minimum number of Steiner points and bounded edge-length,' Information Processing Letters, vol.69, pp.53-57, 1999 
  • 이 논문을 인용한 문헌 (1)

    1. Kim, Joon-Mo 2008. "The application of the combinatorial schemes for the layout design of Sensor Networks" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신, 45(7): 9~16     

 저자의 다른 논문

  • 김준모 (16)

    1. 2005 "지리정보시스템에서 고속도로 연결 문제의 가변적 근사기법" 한국공간정보시스템학회 논문지 = Journal of Korea Spatial Information System Society 7 (2): 57~66    
    2. 2007 "AN APPROXIMATION SCHEME FOR A GEOMETRICAL NP-HARD PROBLEM" Journal of the Korean Society for Industrial and Applied Mathematics 11 (4): 1~8    
    3. 2008 "센서 네트워크 구축에서의 Combinatorial 기법 적용" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신 45 (7): 9~16    
    4. 2009 "근사접근법 분석을 위한 오차허용치의 분배방법" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신 46 (5): 1~7    
    5. 2010 "센서네트워크 상의 TSP 경로구성 방법에 대한 분석" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신 47 (11): 1~6    
    6. 2010 "GOSST를 이용한우편물 교환센터의 가중치 반영 최적 위치의 선정" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신 47 (11): 7~13    
    7. 2010 "스타이너 트리를 이용한 입력 선분의 연결" 정보처리학회논문지. The KIPS transactions. Part A. Part A a17 (5): 213~220    
    8. 2011 "센서네트워크 상의 노드 밀집지역 간 상호연결을 위한 문제" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신 48 (2): 6~13    
    9. 2011 "Balanced Howell Rotations를 이용한 동적 라우팅 정보 생성" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신 48 (2): 14~20    
    10. 2011 "RFID 망에서 Tag 인식을 위한 회고풍의 최대 우도 결정 규칙" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. TC, 통신 48 (2): 21~28    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기