• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Ping, H. (Ping, H..) | Wang, Y. (Wang, Y..) | Zhang, Y. (Zhang, Y..) | Li, D. (Li, D..) | Xie, L. (Xie, L..)

Indexed by:

EI Scopus SCIE

Abstract:

When the edge between two nodes is not measured, is there any hint to know the edge property, and will the inferred edge property be useful? To answer these questions, this paper uniformly defines the properties of unmeasurable edges in generic graphs. For an unmeasurable edge  $(i,j)$ , it is called rangeable if its length is unique in any realization of the graph, rigid if the number of its possible lengths is finite, and flexible if it has infinite possible lengths. The rangeable edge can provide deterministic hidden knowledge as if the edge is measured. A condition for an unmeasured edge being rangeable in 2D space is firstly proposed, based on which a centralized identification algorithm (DRE) is designed. However, the centralized rangeable edge identification has the overhead of global information collection. Therefore distributed condition and algorithm to identify rangeable edges are further investigated. We prove that an unmeasurable edge  $(i,j)$  is rangeable if there are at least two Disjoint Minimally Rigid Branches (DMRBs) between  $i$  and  $j$ . The unmeasurable edge  $(i,j)$  is rigid and flexible when the number of DMRB is one and zero, respectively. A distributed Branching and Blacklisting (BB) algorithm is proposed to find DMRBs, so that rangeable edges are identified distributively. Then, the applications of rangeable, rigid, and flexible edges are discussed. Experimental evaluations show that the centralized and distributed algorithms can identify a rich set of unmeasurable but rangeable edges in distance graphs, even more than the number of directly measured edges. Moreover, BB has a similar identification performance as the centralized DRE algorithm and outperforms existing distributed unmeasurable edge inference algorithms significantly. IEEE

Keyword:

node localizability Image edge detection Generic graph unmeasurable edge Rigidity Inference algorithms Distance measurement rigid Internet of Things Location awareness Sufficient conditions rangeable

Author Community:

  • [ 1 ] [Ping H.]Faculty of Information Technology, Beijing University of Technology, Beijing, China
  • [ 2 ] [Wang Y.]Department of Computer Sciences, Renmin University of China, Beijing, China
  • [ 3 ] [Zhang Y.]Department of Computer Sciences, Renmin University of China, Beijing, China
  • [ 4 ] [Li D.]Department of Computer Sciences, Renmin University of China, Beijing, China
  • [ 5 ] [Xie L.]School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, Singapore

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ACM Transactions on Networking

ISSN: 1063-6692

Year: 2024

Issue: 3

Volume: 32

Page: 1-15

3 . 7 0 0

JCR@2022

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Affiliated Colleges:

Online/Total:251/10730866
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.