(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2005/0195761A1
`Alicherry et al.
`(43) Pub. Date:
`Sep. 8, 2005
`
`US 2005O195761A1
`
`(54) METHOD FOR LOCATION TRACKING
`USING WICINITIES
`
`(76) Inventors: Mansoor Ali Khan Alicherry, Scotch
`Plains, NJ (US); Harsha S. Nagesh,
`Berkeley Heights, NJ (US); Chitra A.
`Phadke, Basking Ridge, NJ (US);
`Viswanath Poosala, Middlesex (IN)
`Correspondence Address:
`Docket Administrator
`(Room 3J-219)
`Lucent Technologies Inc.
`101 Crawfords Corner Road
`Holmdel, NJ 07733-3030 (US)
`(21) Appl. No.:
`10/795,606
`
`(22) Filed:
`
`Mar. 8, 2004
`
`
`
`Publication Classification
`
`(51) Int. Cl. ................................................... H04Q 7/00
`(52) U.S. Cl. ............................................ 370/328; 370/312
`
`(57)
`
`ABSTRACT
`
`A method for location tracking on a distributed basis using
`multiple locations. which utilizes a pairwise application of
`distance constraints and vicinities for determining locations.
`The location of a particular node is represented by a group
`of points (as opposed to a single point) defined by the
`vicinity.
`
`Page 1 of 12
`
`SAMSUNG EX-1069
`
`

`

`Patent Application Publication Sep. 8, 2005 Sheet 1 of 5
`
`US 2005/0195761 A1
`
`FIC.
`
`f.
`
`
`
`100
`
`Page 2 of 12
`
`

`

`Patent Application Publication Sep. 8, 2005 Sheet 2 of 5
`
`US 2005/0195761 A1
`
`FIC. 2
`
`
`
`Page 3 of 12
`
`

`

`Patent Application Publication Sep. 8, 2005 Sheet 3 of 5
`
`US 2005/0195761 A1
`
`FIC. 3
`
`
`
`
`
`
`
`
`
`
`
`
`
`NITIALIZE WICINITY OF EACH GPS NODE
`AS ITS CURRENT POSITION AND EACH
`FLOATING NODE AS FULL AREA
`
`
`
`FOR A VICINITY Vy DEFINE
`EXTENDED (V,n) = Vy + ALL POINTS
`WITHIN DISTANCE R OF ANY POINT IN Vy
`
`
`
`FOR NODE N WITH VICINITY V ON
`RECEIVING A VICINITY V FROM NODE
`NJ, UPDATE N'S VICINITY AS THE
`INTERSECTION OF W AND
`EXTENDED (Vs, n) WHERE R IS DISTANCE
`BETWEEN N AND N.
`
`
`
`HAS ANY NODE'S VICENTY CHANGED?
`
`BROADCAST NEW WICINITY TO ALL
`NEGHBOR NODES
`
`310
`
`320
`
`330
`
`350
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 4 of 12
`
`

`

`Patent Application Publication Sep. 8, 2005 Sheet 4 of 5
`
`US 2005/0195761 A1
`
`FIC. 4
`
`405
`
`410
`
`45
`
`INITIALIZE VICINITY OF EACH GPS NODE
`AS ITS CURRENT LOCATION AND EACH
`FLOATING NODE AS FULL AREA
`
`FOR A VICINITY Vy DEFINE
`EXTENDED (V,R) = Vy + ALL POINTS
`WITHIN DISTANCE R OF ANY POINT IN Vy
`
`FOR A VICINITY Vy DEFINE INNER (V, R)
`= SET OF POINTS WITHIN DISTANCE R
`FROM EVERY POINT IN Vy
`
`HAS NODE N RECEIVED A VICINITY
`FROM NODE N TO WHICH IT CAN
`COMMUNICATE 2
`
`
`
`
`
`FOR NODE N WITH VICINITY
`V, ON RECEIVING A VICINITY
`V FROM NODE NUPDATE
`N'S VICINITY AS THE EXTENSION
`OF V AND EXTENDED (VR)
`WHERER IS THE DISTANCE
`BETWEEN NODES Ni AND NJ
`
`450
`
`FOR NODE N WITH
`VICINITY V UPDATE
`N'S VICINITY AS
`V = V -
`INNER (V.MDR)
`
`HAS ANY NODE'S
`WCINITY CHANGED?
`
`445
`
`BROADCAST NEW WICINITY OF
`NODE TO ALL NEIGHBOR NODES
`
`HAS ANY NODE'S
`WCINITY CHANGED?
`YES
`440
`BROADCAST NEW WICINITY OF
`NODE AS WELL AS THE
`WCINITY OF SUCH NODE'S
`NEIGHBOR NODES
`
`
`
`
`
`450
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 5 of 12
`
`

`

`Patent Application Publication Sep. 8, 2005 Sheet 5 of 5
`
`US 2005/0195761 A1
`
`FIC. 5
`
`A (0,0) B(15,0) C(30,0)
`510
`530
`
`
`
`570
`
`Page 6 of 12
`
`

`

`US 2005/0195761 A1
`
`Sep. 8, 2005
`
`METHOD FOR LOCATION TRACKING USING
`WCINITIES
`
`FIELD OF THE INVENTION
`0001. The present invention relates generally to location
`tracking and, more particularly, to a method for tracking the
`locations of devices in communications networkS Such as
`cellular and ad hoc communications networks.
`
`BACKGROUND OF THE INVENTION
`0002 Wireless cellular telecommunications systems,
`wire-line telecommunications Systems, and the Internet are
`well-known examples of So-called fixed infrastructure net
`WorkS. These types of networks are characterized in part by
`their use of a fixed infrastructure (e.g., wireless base sta
`tions, central offices, local loops, routers and the like) and
`the ability to leverage a known network topology (e.g., in
`making routing decisions among network nodes). Despite
`their many advantages, Such fixed networks can be expen
`Sive to upgrade and can be uneconomical where the number
`of users is minimal (see, for example, J. Liet al., “A Scalable
`Location Service for Geographic Ad Hoc Routing, Pro
`ceedings ACM/IEEE Mobicom, pp. 120-130, August 2000,
`which is hereby incorporated by reference). In contrast,
`well-known ad hoc networks do not utilize a fixed infra
`Structure instead utilizing a variable infrastructure which
`changes as a function of the devices coming together to form
`the particular ad hoc network. As will be appreciated, ad hoc
`networks offer increased flexibility and decreased fixed
`investments to implement (See, for example, Li et al., Supra).
`0003. An important application in either fixed infrastruc
`ture networks or ad hoc networks is So-called “location
`tracking” which is the ability to locate particular devices
`(e.g., a node) throughout the network. Location tracking
`arises in Several contexts in mobile networking. For
`example, location-based routing algorithms have been pro
`posed to reduce the amount of data transferred in computing
`a path in ad hoc networks (see, for example, Y. B. Ko et al.,
`“Location-Aided Routing (LAR) in Mobile Ad hoc Net
`works”, Proceedings ACM/IEEE Mobicom, pp. 66-75, Octo
`ber 1998, which is hereby incorporated by reference). Fur
`ther, well-known cellular applications Such as fleet tracking
`and emergency response Systems rely on location informa
`tion in delivering their respective cellular Services. AS Such,
`the accuracy of the location information is central to the
`performance of all these applications whether being deliv
`ered via a fixed network or ad hoc network.
`0004. There exist a number of well-known location track
`ing techniques. For example, triangulation is the well-known
`technique of locating a particular mobile device through the
`knowledge of the angle of arrival of Signals at the to-be
`located mobile device from three other devices, where the
`locations of the three other devices are known. Trilateration
`is the well-known technique of locating a particular mobile
`device by determining the distance of the to-be-located
`mobile device from at least three reference points whose
`precise location is known. For example, the three reference
`points might be three other mobile devices in proximity to
`the to-be-located mobile device. In terms of locating a
`cellular telephone, two primary forms of trilateration are
`used in conventional, cellular communications. The first
`form of trilateration is performed by the cellular network
`
`itself using its network infrastructure; in particular, the
`network uses the known locations of each base Station
`within its infrastructure to locate a particular mobile tele
`phone. Specifically, the location of three known base Sta
`tions in the same geographic location as the to-be-located
`mobile telephone is used to determine the relative position
`of Such device. The typical locating precision of this tech
`nique is approximately in the range of 50 meters to 300
`meterS.
`0005 The second trilateration form conventionally used
`in locating a particular mobile telephone device within the
`cellular communications network employs the well-known
`Global Positioning System (GPS). GPS is a time-synchro
`nized, Space-based Satellite System that broadcasts spread
`Spectrum codes and consists of a GPS constellation consist
`ing of 24 individual satellites. A ground-based GPS receiver
`at or near the object to be located (e.g., the cellular telephone
`device) determines the difference between the time at which
`each Satellite transmits a particular time signal and the time
`at which Such Signal is received. Using the calculated time
`differentials in standard GPS, the object's location is deter
`mined typically to within about 100 meters. This accuracy
`can be further improved upon by using the well-known
`commercially available Differential GPS, which improves
`the GPS location accuracy to within 10 meters.
`0006 Still other techniques have been proposed for locat
`ing mobile devices in the contexts of indoor ad hoc net
`works. For example, RADAR (see, P. Bahl et al., “RADAR:
`An In-Building RF-Based User Location and Tracking Sys
`tem”, IEEE Info Com, March 2000, which is hereby incor
`porated by reference) is a well-known technique for tracking
`indoor environments where a Single fingerprint of an entire
`region is constructed and the location of a particular node is
`determined based on the Signal Strength observed at its
`location. Further, for example, CRICKET (see, N. B. Priy
`antha et al., “The CRICKET Location-Support System’,
`ACM MOBICOM, August 2000, which is hereby incorpo
`rated for reference) is another well-known indoor tracking
`technique where nodes have so-called “listeners” which
`receive periodic radio and ultrasound Signals from base
`Stations in a network. Thereafter, Such signals are employed
`to determine a particular node's location using an estimate
`of such nodes proximity to the base stations. In CRICKET,
`the objective is to make an association with the closest base
`Station and not to precisely estimate the true position of the
`mobile node.
`0007. In addition to the above-mentioned RADAR and
`CRICKET techniques, LAR is a reactive routing protocol
`used in mobile ad hoc networks where all the nodes are
`aware of their respective locations, See, for example, Y. B.
`Ko et al., Supra. In LAR, the Source of a packet Session
`initiates a route request for the destination. This request, in
`turn, is forwarded by other nodes that lie within a so-called
`“request region', Such request region being computed by the
`Source from the previous known location and Velocity of the
`destination. In the event that a route reply is not received
`within a Specified timeout, LAR either resorts to a global
`flooding protocol or gradually expands the request region
`and repeats the discovery proceSS until the route is com
`puted.
`0008 Geographic forwarding is a stateless packet for
`warding technique employed in large wireleSS networks, See,
`
`Page 7 of 12
`
`

`

`US 2005/0195761 A1
`
`Sep. 8, 2005
`
`for example, J. Li et al., Supra; and C. T. Cheng et al.,
`“SLALOM: A Scalable Location Management Scheme for
`Large Scale Mobile Ad hoc Networks”, Proceedings of
`Wireless Communications and Networking Conference,
`March 2002, which is hereby incorporated by reference. In
`geographic forwarding, nodes are aware of their respective
`locations and a packet intended for a destination is for
`warded to the destination's location by the intermediate
`nodes. The intermediate nodes forward the packet to a
`neighbor node that is determined to be the closest to the
`destination in terms of a Euclidean distance.
`0009. Other location-based techniques include using
`Short-range, peer-to-peer communications in combination
`with the imposition of particular distance constraints
`between nodes to identify a location of a particular node
`(see, for example, L. Doherty, “Algorithms for Position and
`Data Recovery in Wireless Sensor Networks', Master's
`Report, University of California Berkeley, June 2000, which
`is hereby incorporated by reference). However, Doherty's
`technique is best Suited for centralized execution which
`presents certain challenges in a distributed network. Another
`technique detailed in D. Niculescu et al., “Ad hoc Position
`ing System (APS) Using AOA”, IEEE Infocom, April 2003,
`which is hereby incorporated by reference, is directed to a
`node measuring the angle of arrival of Signals from various
`points (where Such points have knowledge about their
`respective locations) and using triangulation to determine
`the node's location.
`0010. As described above, there exist numerous location
`based routing and location information techniques employed
`in wireleSS or ad hoc communications networkS. Central to
`the above-described techniques, however, is that they pri
`marily attempt to compute a single point location, which
`may or may not be the true location. Obviously, if the
`computed Single location is incorrect, that information will
`adversely impact network performance (e.g., data will be
`forwarded to incorrect nodes, or data may take extended
`paths leading to dropped packets). Further, Such techniques
`are primarily directed to centralized execution as opposed to
`a more distributed execution.
`0.011
`Thus, there exists a need for an enhanced location
`based routing technique which addresses multiple locations
`and provides for distributed execution.
`
`SUMMARY OF THE INVENTION
`0012. The present invention provides a method for loca
`tion tracking on a distributed basis using multiple locations.
`More particularly, in accordance with an aspect the inven
`tion, a pairwise application of distance constraints utilizes
`So-called vicinities for determining locations. In accordance
`with an aspect of the invention, Vicinities are determined,
`and used in location tracking, as a function of proximity
`constraints only. In accordance with an embodiment of the
`invention, the vicinities of each node in the communications
`network are initialized as follows: (a) the vicinity of a fixed
`node (e.g., GPS node) is defined as its current location; and
`(b) the vicinity of each floating node (e.g., a cellular tele
`phone) is defined as its entire region or full area (i.e., Since
`Such floating nodes do not have knowledge of their location
`at initialization). Further, in accordance with the invention,
`for a given vicinity Van extended vicinity is defined as the
`points in the given vicinity combined with the points within
`
`a distance R of any point in V. Thus, for each node N with
`vicinity V, upon Such node receiving a broadcast of vicinity
`V, from node N, the vicinity of N, is updated as the
`intersection of V, and the extended vicinity(V, R), where R
`is the distance between node N, and node N. As the vicinity
`of a node changes Such node will broadcast it's updated
`vicinity to the other neighboring nodes. The vicinity updat
`ing continues until Such time that the vicinities associated
`with the respective nodes stop Shrinking (i.e., Stops reducing
`in the number of locations within a particular vicinity). In
`accordance with the various aspects of the invention, the
`location of a particular node is represented by a group of
`points (as opposed to a single point) defined by the vicinity.
`0013 In accordance with a further aspect of the inven
`tion, vicinities are determined, and used in location tracking,
`as a function of both proximity constraints and non-proX
`imity constraints, in a communications network in accor
`dance with the aspects of the present invention. More
`particularly, in accordance with this further aspect of the
`invention, if node N, is unable to communicate with N, it can
`be concluded that node N is not within a circle of radius mdr
`of N. Thus, if N is a floating node then N, cannot be at any
`point within a maximum distance range as defined by the
`particular transmission device (hereinafter referred to as
`“mdr”) from every point in N,’s current vicinity. Therefore,
`points can be eliminated from N's vicinity that do satisfy
`Such a requirement. Again, the location of the particular
`node, in accordance with the aspects of the invention, is
`represented by a group of points (as opposed to a single
`point) defined by the vicinity.
`0014 Advantageously, in accordance with the invention,
`each node has a vicinity, at any point in time, which may be
`utilized in location tracking and routing in the communica
`tions network. Importantly, in accordance with the inven
`tion, the location of a particular node is represented by a
`group of points (as opposed to a single point) defined by the
`vicinity thereby minimizing the adverse impact of location
`errors (i.e., as in the single point location techniques) and
`allowing for a distributed solution. More particularly, the
`distributed advantage of the invention stems from the fact
`that each node determines and updates its location (through
`vicinities) utilizing information local to Such node thereby
`eliminating the need to communicate with a central Server
`for Such purposes.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0015 FIG. 1 shows an illustration of proximity and
`non-proximity distance constraints,
`0016 FIG. 2 shows the pairwise application of the dis
`tance constraints of FIG. 1 in accordance with the principles
`of the invention;
`0017 FIG.3 shows a flowchart of illustrative operations
`for determining vicinities, as a function of proximity con
`Straints only, in a communications network in accordance
`with the principles of the present invention;
`0018 FIG. 4 shows a flowchart of illustrative operations
`for determining vicinities, as a function of both proximity
`constraints and non-proximity constraints, in a communica
`tions network in accordance with the principles of the
`present invention; and
`
`Page 8 of 12
`
`

`

`US 2005/0195761 A1
`
`Sep. 8, 2005
`
`0019 FIG. 5 shows an illustrative location tracking
`example utilizing the illustrative operations of FIG. 3 and
`FIG. 4 for determining vicinities in accordance with the
`principles of the invention.
`
`DETAILED DESCRIPTION
`0020. The present invention provides a method for loca
`tion tracking on a distributed basis using multiple locations.
`To facilitate the understanding of the present invention
`Several terms will first be introduced and discussed in Some
`detail. In accordance with an aspect of the invention, a
`So-called “vicinity' is defined as the area containing an
`actual location (e.g., a node). More particularly, as used
`throughout this disclosure, a vicinity is defined as:
`0021 (1) Vicinity. Let n be a node in a network in
`a region R. Then, the vicinity V of n is any subset of
`points in R that contains the actual location of that
`particular node.
`0022. A vicinity, in accordance with the invention, can be
`a disconnected set of points (i.e., not contiguous points or
`regions of points) or a bounded area (i.e., contiguous points
`or regions of points) ranging from a node's exact location to
`an entire cell area. Further, as used throughout this disclo
`Sure, a So-called "feasible vicinity' is a specific vicinity
`which comprises the locations of a particular node which are
`present in the So-called "feasible Solution Set' for a given
`constraint Set. AS used throughout this disclosure, a "feasible
`Solution' is defined as:
`0023 (2) Feasible Location & Feasible Solution.
`For a given class(es) of constraints, a feasible Solu
`tion is any location vector of the nodes (1, 1... 1)
`that Satisfies all of those constraints. In addition, a
`“feasible set' is the set of all possible feasible
`Solutions.
`0024. Thus, for every element in a feasible vicinity there
`exists a positioning of the other nodes Such that the con
`Straints are Satisfied. In terms of applying the constraints, as
`will be appreciated, distance constraints can be defined Such
`that at any given instant a specific distance relationship will
`hold between each pair of nodes in a network. Two Such
`distance constraints are as follows:
`(0025) (3) Proximity-If two nodes (n, n) can com
`municate using So-called Static radios (i.e., a device
`can only transmit at a maximum distance range of
`mdr) they are within a distance of mdr of each other.
`If they can communicate using dynamic radios (i.e.,
`a device can modify its power to change its trans
`mission range from Zero to mdr) where the adjust
`able distance is defined as d, they are within d of each
`other. Lot dist(a,b) return the Euclidian distance
`between two locations a and b. Then,
`dist(nini)sy, where x=d for dynamic radios and mdr
`for static radios.
`0026 (4) Non-proximity-If two nodes (ni, n) can
`not communicate with each other, they are more than
`mdr away from each other. Then,
`
`0027. As will be appreciated, using the proximity and
`non-proximity relationships as Set forth above, a proximity
`graph can be constructed with a vertex corresponding to
`
`each node in the a given network and an edge between (n,
`n) when they are in proximity (in accordance with definition
`(3) above).
`0028. For example, FIG. 1 shows an illustration of
`proximity and non-proximity distance constraints. More
`particularly, FIG. 1 shows a network 100 consisting of GPS
`node G 110 and two floating nodes B 120 and B 130, each
`Such floating node containing a dynamic radio (see defini
`tion () above) and where the exact location of each node is
`identified in FIG. 1 by their respective node names. In FIG.
`1, the maximum range is illustratively Set at 15 m which, in
`turn, provides for node B 120 communicating with the other
`two nodes (i.e., G 110 and B 130) while B can commu
`nicate only with B. Applying a proximity constraint
`between B, G it can be shown that B’s location can only
`be inside a circle of radiuS 10 m from G. Thus, applying the
`Same proximity constraint between B, B2 it can be shown
`that B must be within a band of 10 m around B's possible
`location which reduces to a circle of 20 m radius around G.
`Therefore, vector G, C, B and G, C, D) are two possible
`feasible Solutions. Similarly, by applying the non-proximity
`constraint between G and B it can be shown that Bcannot
`be within a circle of 15 m around G. In Such case, vector
`G, C, B is not a feasible solution whereas G, C, D) is
`feasible.
`0029. Existing location tracking techniques (as described
`previously) can be generally classified as computing a single
`feasible Solution under proximity constraints (i.e., a So
`called “single point Solution”). AS Such, all feasible Solutions
`are equally valid under a given Set of constraints Such that
`there exists no guarantee that the chosen Solution is closer to
`the actual location than any other possible location. In Such
`Single point Solutions, the locations used are a function of a
`feasible Solution computed under a Set of constraints. That
`is, this type of Solution is essentially a randomly chosen
`element of the feasible Set. AS long as the nodes have not
`moved, the same locations are used at each invocation to
`compute distances, path lengths and the like. As a result, if
`the particular chosen feasible Solution is incorrect, the entire
`networks (or location System) performance is adversely
`affected.
`0030 To address the above, the Applicants herein have
`realized an improved location tracking technique which, in
`accordance with the various aspects of the present invention,
`utilizes multiple feasible Solutions Such that a randomly
`chosen feasible Solution is employed for each invocation.
`More particularly, in accordance with an aspect of the
`invention, multiple location vectors (i.e., multiple feasible
`Solutions are Selected on a random basis from the vicinities
`of other nodes) that are valid under a given set of inter-node
`distance constraints are utilized for locating a particular
`location (e.g., a node) in a distributed (as opposed to
`centralized) fashion.
`0031 AS introduced above, in accordance with an aspect
`of the invention, distance constraints are applied to pairs of
`nodes for computing SuperSets of feasible vicinities. In
`particular, given a Set of constraints, the vicinities in accor
`dance with this aspect of the invention have the following
`property:
`0032 (5) Consider a location 1, occurring in the
`vicinity V of a node n. When the proximity con
`Straint is used, for every node in there exists a
`
`Page 9 of 12
`
`

`

`US 2005/0195761 A1
`
`Sep. 8, 2005
`
`location l; in the vicinity V of n. Such that l;and l are
`mdr (see definition (3) above). If the non-proximity
`constraint is used, then for every node n; that is not
`a neighbor of n, there exists at least one location V,
`Such that l; and l are more than mdr away (see
`definition (4) above).
`0033. The aforementioned aspect of the invention related
`to the pairwise application of constraints (as opposed to
`applying all the constraints together) is illustrated in FIG. 2
`which shows a region 200 with three GPS nodes (G205, G.
`210 and G. 215), and four floating nodes (B. 220, B225,
`B 230 and B, 235). The edges (200-1, 200-2, 200-3 and
`200-4) connecting the four floating nodes are each, illustra
`tively, 10 m in length. The vicinities (vicinity 240,245, 250
`and 255), in accordance with the invention, of these nodes
`are shown in the shaded regions of FIG. 2. Further, let
`B 260 be a location chosen from the vicinity 250 of B235.
`Thus, as shown in FIG.2, B205, and B-265 are 10 m from
`B260 as determined by applying the principles of the
`invention. Additionally, the only location in vicinity 240
`(i.e., the vicinity of node B 220) at a distance of 10 m from
`B205 is B, 270, and from B-265 is B"275. Therefore,
`given B, 270 and is B"275 are two different points in
`vicinity 240 there is no feasible solution having B-260 as
`the possible position of node B235.
`0034.
`In accordance with the invention, the pairwise
`application of constraints are used for determining vicinities.
`The determination and use of Such vicinities in location
`tracking is a further aspect of the invention. To that end,
`FIG. 3 shows a flowchart of illustrative operations for
`determining vicinities, as a function of proximity constraints
`only, in a communications network in accordance with the
`principles of the present invention. More particularly, in
`accordance with this embodiment of the invention, the
`vicinities of each node in the communications network are
`initialized (see block 310) as follows: (a) the vicinity of GPS
`node is defined as its current location; and (b) the vicinity of
`each floating node is defined as its entire region or full area
`(i.e., Since Such floating nodes do not have knowledge of
`their location at initialization). Further, in accordance with
`the invention, for a given vicinity V, an extended vicinity is
`defined (see, block 320) as the points in the given vicinity
`combined with the points within a distance R of any point in
`V. Thus, for each node N with vicinity V, upon such node
`receiving a broadcast of vicinity V, from node Ni, the
`vicinity of N is updated as the intersection of V, and the
`extended vicinity(V, R), where R is the distance between
`node N, and node N, (see, block 330). As the vicinity of a
`node changes (see, block 340) such node will broadcast it's
`updated vicinity to the other neighboring nodes (see, block
`350). Such vicinity updating continues until such time that
`the vicinities associated with the respective nodes Stop
`Shrinking (i.e., stops reducing in the number of locations
`within a particular vicinity). The reductions in locations and
`their application in bounding a vicinity determination is
`described in further detail hereinbelow.
`0.035
`Advantageously, in accordance with the invention,
`each node has a vicinity, at any point in time, which may be
`utilized in location tracking and routing in the communica
`tions network. Importantly, in accordance with the inven
`tion, the location of a particular node is represented by a
`group of points (as opposed to a single point) defined by the
`vicinity.
`
`0036 FIG. 4 shows a flowchart of illustrative operations
`for determining vicinities, as a function of both proximity
`constraints and non-proximity constraints, in a communica
`tions network in accordance with the principles of the
`present invention. More particularly, in accordance with this
`further embodiment of the invention, if node N is unable to
`communicate with N, it can be concluded that node N, is not
`within a circle of radius mdr of N. Thus, if N is a floating
`node then N, cannot be at any point within mdr from every
`point in N’s current vicinity, therefore, Such points can be
`eliminated from N’s vicinity. As shown in FIG. 4, initial
`ization (see, block 405) and defining the extended vicinity
`function (see, block 410) occurs in the same fashion as
`detailed above with regard to the same operations of FIG. 3.
`The operation detailed in block 415 defines a certain
`inner(VR) function which is directed to applying the non
`proximity constraints in the event certain nodes are unable
`to communicate as described above. In accordance with this
`embodiment of the invention, a determination is made (see,
`block 420) as to whether a node N receives a vicinity from
`a node N to which it can communicate. If so, the application
`of proximity constraints are applied (see, blocks 425, 435
`and 445, respectively) in the same manner as these same
`operations are described above with reference to FIG. 3. If
`Such nodes are unable to communicate, non-proximity con
`straints are applied (see, blocks 430, 440 and 450, respec
`tively).
`0037 More particularly, as shown in FIG. 4, node N's
`vicinity is updated (see, block 430) to remove particular
`points using the function of inner(VR). Thereafter, in accor
`dance with this embodiment of the invention, the updated
`vicinity is broadcast (see, block 450) together with the
`vicinities of all the neighboring nodes of N. Thus, in
`accordance with invention, for proximity constraints a node
`will broadcast only that node's vicinity to the other nodes,
`and, for non-proximity constraints the node will broadcast
`the vicinities of its neighboring nodes in addition to its own
`vicinity.
`0038 FIG. 5 shows an illustrative location tracking
`example utilizing vicinities and the illustrative operations of
`FIG. 3 and FIG. 4. In particular, consider a region (e.g., a
`region of a wireless communications network) containing
`three nodes (A, B, C) at locations (0,0), (15.0) and (30,0)
`respectively (see, nodes 510,520 and 530 in FIG. 5), where
`node 510 is a GPS node and nodes 520 and 530 are floating
`nodes. Further, let the maximum radio range mdr be 20 m.
`Proximity graph 540 illustrates the results of applying
`proximity constraints between the three nodes in accordance
`with the invention. In particular, as shown in proximity
`graph 540, node B's vicinity 560 is the set of points within
`15 m from node A. Further, the vicinity 570 of node C 530
`is the set of points 15 m from the points in node B's vicinity
`(i.e., a circle of radius 30 around the origin).
`0039. Further, proximity graph 550 shows the results of
`applying the principles of the invention directed to using
`both the proximity constraints and non-proximity con
`straints. In particular, node C 530 cannot communicate with
`node A510 So it cannot be within a circle of 20 m around
`node A510. Therefore, in accordance with the invention,
`node C's vicinity 580 is determined by eliminating points
`that within 20 m from node A and such vicinity is reduced
`to the donut-shaped ring of inner radius 20 and Outer radius
`30 as shown in proximity graph 550. Interestingly, applying
`
`Page 10 of 12
`
`

`

`US 2005/0195761 A1
`
`Sep. 8, 2005
`
`node C's refined vicinity 580 and the proximity constraints
`between node B and node C, node B's vicinity is further
`reduced to contain only points that are within 15 m from any
`point in node C. Therefore any points within a circle of
`radius 5 m around the origin are eliminated from node BS
`vicinity 590 due their failure in satisfying the proximity
`constraint.
`0040 AS will be appreciated from the illustrative
`example of FIG. 5, vicinities are represented as sets of
`locations, and only when the proximity constraint is
`enforced is there a guarantee that the vicinities will be of
`convex (e.g., circular) shape. AS will be appreciated, a
`convex Set is a Set in which every Segment which connects
`points of the set lies entirely within the set. As will be
`understood, the vicinities determined in accordance with
`invention may also be represented using boundaries of
`shapes by employing well-known computer graphic tech
`niques, or by using a bounding box to approximate the
`vicinities.
`0041 AS will also be understood, the various aspects of
`the invention described above involve the performance of a
`Significant amount of data transferS and interSections. There
`fore, in accordance with an embodiment of the invention, in
`recognition that certain data transferS lead to an interSection,
`the data transferred is viewed as the Sole complexity metric.
`That is, in accordance with this embodiment of the inven
`tion, the number of data transferS is a measure of the
`efficiency of the methodology. Therefore, a reduction of the
`overall amount of data transferred is achieved by utilizing an
`off-line schedule derived as a function of the proximity
`graph to dictate when nodes should broadcast their vicinity.
`To the end, the Applican