微信服务号

微信订阅号

2025-4-6- 11
Home > Archive>Volume 22, Issue zk1, 2011 >131-141
PDF HTML XML Export Cite reminder
K-CLOSE:Algorithm for Finding the Close Regions in Wireless Sensor Networks Based Uncertain Graph Mining Technology
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [15]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Due to the instability of wireless links and the complexity of geographical environment where wireless sensor networks are deployed,sensor nodes can not guarantee communication with their neighboring nodes with high probabilities.Resolving the problem of finding the sensor nodes that communicate well in practical settings can play an important role in node clustering and the optimization of routing protocols.It is important to note the discovery which nodes in a region are more close to each other in actual movement.A new algorithm called K-CLOSE is proposed in this paper to solve the problem which finding the most k close regions.First,K-CLOSE abstracts wireless sensor networks into uncertain graphs in a distributed manner.Then,the closeness threshold is determined by an approximation algorithm proposed in this paper,which has approximate rate 2.Finally,the k close regions where sensor nodes communicate with high probabilities are discovered using tree searching and branch-and-bound methods.Moreover,the experimental results show that the proposed algorithm is efficient in practice.

    Reference
    [1] Girvan M,Newman MEJ.Community structure in social and biological networks.Proc.Natl.Acad.Sci.99,2002,7821.
    [2] Wang Y,Gao J,Mitchell JSB.Boundary recognition in sensor networks by topological methods.In:Proc.of the MobiCom 2006. New York:ACM Press,2006.122-133.
    [3] Fernandess Y,Malkhi D.K-Clustering in wireless ad hoc networks.In:Proc.of the 2nd ACM Int’l Workshop on Principles of Mobile Computing 2002.New York:ACM Press,2002.31-37.
    [4] Chang C-S,Hsu C-Y,Cheng J,Lee D-S.A general probabilistic framework for detecting community structure in network.In:Proc. of the IEEE INFOCOM 2011.Washington:IEEE Press,2011.
    [5] Li J,Khuller ADS.On computing compression trees for data collection in wireless sensor networks.In:Proc.of the IEEE INFOCOM 2010.Washington:IEEE Press,2010.2115-2123.
    [6] Liu CL,Cao GH.Distributed monitoring and aggregation in wireless sensor networks.In:Proc.of the IEEE INFOCOM 2010. Washington:IEEE Press,2010.2097-2105.
    [7] Nguyen NP,Dinh TN,Xuan Y,Thai MT.Adaptive algorithms for detecting community structure in dynamic social networks.In: Proc.of the IEEE INFOCOM 2011.Washington:IEEE Press,2011.
    [8] Andersen R,Chellapilla K.Finding dense subgraphs with size bounds.In:Proc.of the Workshop on Algorithms and Models for the Web-Graph,WAW 2009.Barcelona:Springer-Verlag,2009.25-36.
    [9] Khuller S,Saha B.On finding dense subgraphs.In:Proc.of the Int’l Colloquium on Automata,Languages and Programming, ICALP 2009.Rhodes:Springer-Verlag,2009,(1):597-608.
    [10] Zou ZN,Li JZ,Gao H,Zhang S.Mining frequent subgraph patterns from uncertain graph data.IEEE Trans.on Knowledge and Data Engineering,2010,22(9):1203-1218.
    [11] Han M,Zhang W,Li JZ.RAKING:An efficient K-maximal frequent pattern mining algorithm on uncertain graph database. Chinese Journal of Computers,2010,33(8):1387-1395(in Chinese with English abstract).
    [12] Potamias M,Bonchi F,Gionis A,Kollios G.k-Nearest neighbors in uncertain graphs.In:Proc.of the Vldb Endowment,PVLDB. 2010,3(1):997-1008.
    [13] Zou ZN,Li JZ,Gao H,Zhang S.Finding top-k maximal cliques in an uncertain graph.In:Proc.of the Int’l Conf.on Data Engineering 2010.Washington:IEEE Press,2010.649-652.
    [14] Han M,Li JZ,Zou ZN.Finding the K close subgraphs in an uncertain graph.Journal of Frontiers of Computer Science & Technology,2011,5(9):791-803.
    [15] Feige U,Kortsarz G,Peleg D.The dense k-subgraph problem.ALGORITHMICA,2001,29(3):410-421.
    Cited by
Get Citation

韩蒙,李建中,邹兆年.K-CLOSE:基于不确定图挖掘技术的传感器网络紧密区域发现算法.软件学报,2011,22(zk1):131-141

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 02,2011
  • Revised:July 29,2011
  • Online: January 02,2012
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033338Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063