School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China;School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China 在期刊界中查找 在百度中查找 在本站中查找
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.
[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.