(12)
`
`United States Patent
`Kullman et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,072,666 B1
`Jul. 4, 2006
`
`US007072666B1
`
`(54) METHOD AND SYSTEM FOR
`COMMUNICATING LOCATION IN A
`CELLULAR WIRELESS SYSTEM
`
`(*) Notice:
`
`(75) Inventors: o Styliss Sisted
`. Sonndor, Ulalne,
`; Ric
`Haught, Lawrence, KS (US)
`(73) Assignee: Spring Spectrum L.P., Overland Park,
`KS (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 437 days.
`(21) Appl. No.: 09/886,637
`
`y x- - -
`
`9
`
`5,764,188 A * 6/1998 Ghosh et al. ............... 342/457
`5,873,040 A
`2f1999 Dunn et al.
`6,466,796 B1 * 10/2002 Jacobson et al. ........ 455,456.3
`2002fO151313 A1* 10, 2002 Stead ......................... 455,456
`2002/0193121 A1* 12/2002 Nowak et al. .............. 455,456
`OTHER PUBLICATIONS
`Scot Drysdale, “Voronoi Diagrams: Applications from
`Archaology to Zoology.” Regional Geometry Institute,
`Smith College, Jul. 19, 1993.
`* cited by examiner
`Primary Examiner Charles N. Appiah
`Assistant Examiner—Bryan Fox
`
`(22) Filed:
`
`Jun. 21, 2001
`
`(57)
`
`ABSTRACT
`
`(51) Int. Cl.
`(2006.01)
`H04O 7/20
`(52) U.S. Cl. ............................... 4ss/4s61:455/4042,
`455/456.3
`(58) Field of Classification Search ............. assasoi,
`455/456.3, 457: 342/450
`See application file for complete search histO
`pp
`p
`ry.
`References Cited
`U.S. PATENT DOCUMENTS
`5,508,707 A * 4, 1996 LeBlanc et al. ............ 342/457
`
`(56)
`
`A method and system for communicating location informa
`tion in a cellular wireless system. Each sector in a coverage
`area is characterized by a polygon of influence with respect
`to the othersectors. The polygon of influence is then used as
`a basis to characterize the scope or position of the sector and,
`particularly, the location of a mobile station that is operating
`in the sector. A location-based-service provider can then use
`that polygon of influence based location information to
`facilitate providing a location-based service.
`
`33 Claims, 8 Drawing Sheets
`
`
`
`Page 1 of 19
`
`SAMSUNG EX-1207
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 4, 2006
`Jul. 4, 2006
`
`Sheet 1 of 8
`Sheet 1 of 8
`
`US 7,072,666 B1
`US 7,072,666 B1
`
`
`
`
`
`FIG. 1
`FIG. 1
`
`Page 2 of 19
`
`Page 2 of 19
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 4, 2006
`Jul. 4, 2006
`
`US 7,072,666 B1
`
`Sheet 2 of 8
`Sheet 2 of8
`
`US 7,072,666 B1
`
`
`
`Page 3 of 19
`
`Page 3 of 19
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 4, 2006
`Jul. 4, 2006
`
`Sheet 3 of 8
`Sheet 3 of8
`
`US 7,072,666 B1
`US 7,072,666 B1
`
`
`
`
`
`FIG. 4
`FIG. 4
`
`Page 4 of 19
`
`Page 4 of 19
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 4, 2006
`Jul. 4, 2006
`
`Sheet 4 of 8
`Sheet 4 of8
`
`US 7,072,666 B1
`US 7,072,666 B1
`
`
`
`
`
`C3
`C3
`
`28
`28
`
`FIG. 6
`FIG. 6
`
`Page 5 of 19
`
`Page 5 of 19
`
`

`

`U.S. Patent
`U.S. Patent
`
`US 7,072,666 B1
`US 7,072,666 B1
`
`fl
`
`FG. 7
`FIG. 7
`
`
`
`
`
`Page 6 of 19
`
`Page 6 of 19
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 4, 2006
`Jul. 4, 2006
`
`Sheet 6 of 8
`Sheet 6 of8
`
`US 7,072,666 B1
`US 7,072,666 B1
`
`
`
`
`
`
`
`
`FG. 9
`FIG. 9
`
`F.G. 1 O
`FIG. 10
`
`Page 7 of 19
`
`Page 7 of 19
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 4, 2006
`Jul. 4, 2006
`
`Sheet 7 of 8
`Sheet 7 of8
`
`US 7,072,666 B1
`US 7,072,666 B1
`
`
`
`
`
`F.G. 11
`FIG. 11
`
`Page 8 of 19
`
`Page 8 of 19
`
`

`

`U.S. Patent
`
`Jul. 4, 2006
`
`Sheet 8 of 8
`
`US 7,072,666 B1
`
`AONZ9DYSNA
`
`S3ASDIAUZS
`
`HYOMLAN
`
`BEL
`
`“NOILWOOT
`
`SDIAYNSS
`
`INYOALW1d
`
`Vb
`
`a1evL
`
`
`
`NOILYSO1INYOSALWId
`
`SWJDIAYSS
`
`“NOILVYDOT
`
`NOILYSO17-,aasve-ld
`
`LANYSLNI
`
`Page 9 of 19
`
`Page 9 of 19
`
`
`
`
`

`

`US 7,072,666 B1
`
`1.
`METHOD AND SYSTEM FOR
`COMMUNICATING LOCATION IN A
`CELLULAR WIRELESS SYSTEM
`
`BACKGROUND
`
`10
`
`1. Field of the Invention
`The present invention relates to mobile communications
`and, more particularly, to methods and systems for commu
`nicating location in a cellular wireless communication sys
`tem.
`2. Description of Related Art
`Cellular wireless is an increasingly popular means of
`personal communication in the modern world. In a cellular
`wireless network, a coverage area is divided into a number
`15
`of sectors defined by radiation patterns from base stations. A
`mobile station, such as a cellular telephone, personal digital
`assistant ("PDA), cellular modem, or other such device,
`may then communicate with the base station via a radio
`frequency air interface. In turn, each base station is typically
`coupled with other access equipment, such as a gateway or
`switch, to provide connectivity with a transport network
`such as the public switched telephone network (“PSTN) or
`the Internet. A person using a mobile station can thereby
`communicate over the transport network from virtually any
`place inside the cellular coverage area.
`An important feature of contemporary cellular wireless
`networks is an ability to locate the geographical position of
`a mobile station. Such a feature was initially developed to
`assist emergency services in locating a mobile station. For
`example, in the United States, the Federal Communications
`Commission (“FCC) has mandated the implementation of
`“Enhanced 911” (“E911) services, which includes a
`requirement for cellular wireless carriers to report mobile
`station location to a public safety access point (“PSAP)
`when connecting a call from a mobile station to the PSAP.
`The E911 mandate was divided into two phases. Accord
`ing to Phase 1, a cellular wireless carrier must identify the
`location of a mobile 911 caller with an accuracy of the sector
`in which the caller is located. According to Phase 2 (as now
`incorporated in Industry Standard TLA/ELA/IS-J-STD-036
`(J-STD-036), entitled “Enhanced Wireless 9-1-1, Phase 2'),
`a cellular carrier must identify the location of a mobile 911
`caller with an accuracy of at least 50 or 100 meters,
`depending on the mechanism used to determine location.
`In order to comply with Phase 2, a wireless carrier can use
`network-based positioning mechanisms (such as triangular
`ization techniques, etc.) or handset-based positioning
`mechanisms (such as GPS), or a combination of both.
`Unfortunately, however, many carriers are not yet equipped
`with the necessary positioning technology, and it will be
`some time before all or even most mobile stations are
`equipped with GPS positioning technology or before cellular
`carriers will be able to locate all mobile stations with the
`necessary degree of granularity.
`Consequently, many carriers have focused principally on
`compliance with Phase 1 of the mandate.
`Most carriers can readily comply with Phase 1, because a
`carrier usually maintains in a home location register
`(“HLR) or other profile store an indication of the sector in
`which each active mobile station is operating. Thus, when a
`carrier receives a 911 call from a mobile station, the carrier
`can refer to the profile store in order to identify the sector
`where the mobile station is operating. The carrier can then
`set up the call to a 911 service center (as PSAP) and provide
`the center with an indication of that sector. Typically, the
`carrier will give the PSAP an indication of (i) the geographic
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`position or street address of the base station tower and (ii)
`the azimuth (angle) at which the sector extends from the
`base station tower. Emergency service personnel can then
`work to locate the caller in that general direction from the
`base station tower.
`Emergency services are thus one sort of “location-based
`service,” as they can use a location as a basis to provide a
`service. In particular, knowing the geographic location of the
`sector from which a mobile emergency call originates, the
`emergency service can seek to locate and assist the caller.
`The availability of location information to support E911
`services has given rise to the development of many other
`location-based services as well. For instance, given the
`location of a mobile station, a location-based service pro
`vider (e.g., a wireless cellular carrier or third party) can
`provide the mobile station user with a weather or traffic
`report in the user's vicinity. As another example, a location
`based service provider can report a list of services or
`establishments (e.g., restaurants, parks, theatres, etc.) in the
`user's vicinity. As still another example, a location-based
`service provider can provide a mobile station user with a
`map of the user's location or with directions for travel
`between the user's location and another location. And as yet
`another example, knowing that a mobile station is operating
`in a particular location, a location-based service provider can
`send the mobile station a location-based message. Such as an
`advertisement or coupon for a nearby establishment. Other
`location-based services exist currently or will be developed
`in the future as well.
`Just as a cellular wireless carrier can provide a PSAP with
`an indication of where a mobile station is located, the carrier
`can provide other location-based service providers with an
`indication of where a mobile station is located. For instance,
`when connecting a call from a mobile station to a location
`based service platform (or otherwise being involved with a
`communication session with a location-based service), the
`carrier can transmit to the service platform an indication of
`the sector in which the mobile station is currently operating.
`As with E911 service, the carrier might provide the geo
`graphic coordinates or street address of the sector's base
`station tower together with an azimuth of the sector. Alter
`natively, the carrier might translate the base station location
`into a postal Zip code and report that postal Zip code to the
`location-based service provider. The location-based service
`provider may then perform a service based on that location
`information.
`When sector information has been used as a basis to
`describe the location of a mobile station, the description has
`been inherently vague, because it is not immediately clear
`where in the sector the mobile station is actually located. For
`emergency services, this presents a problem, as emergency
`service personnel may have trouble locating a mobile caller
`within a given sector. Similarly, Some other location-based
`services may depend on knowing more precisely where a
`given mobile station is located, so the commercial value of
`those services may diminish due to the imprecision of the
`location information.
`Therefore, a need exists for an improved method of
`communicating location in a cellular wireless system, so as
`to facilitate location-based services.
`
`SUMMARY
`
`The present invention relates to a method and system for
`communicating location information in a cellular wireless
`system. According to an exemplary embodiment of the
`invention, when a mobile station is operating in a given
`
`Page 10 of 19
`
`

`

`3
`sector, the mobile station's location can be characterized by
`reference to a “polygon of influence' drawn for the sector,
`i.e., by reference to a polygon in which Substantially all
`points are closer to the origin of the sector than to the origins
`of adjacent sectors. When prompted to report the location of
`a mobile station, a cellular carrier may thus report an
`indication of the polygon of influence, such as the geo
`graphic coordinates of a point within the polygon of influ
`CCC.
`Thus, in one respect, an exemplary embodiment of the
`invention can take the form of a method of communicating
`a geographic location of a given sector in a cellular wireless
`system, so as to facilitate a location-based service with
`respect to the given sector. The method can involve estab
`lishing a PI-based location to represent the given sector and
`communicating the PI-based location as a representation of
`the geographic location of the given sector. A location-based
`service (such as locating a mobile station in the sector,
`providing an emergency service, weather reporting, traffic
`reporting or route planning, for instance) can then be per
`formed based on the PI-based location.
`In another respect, an exemplary embodiment of the
`invention can take the form of a method of communicating
`mobile station location in a cellular wireless system, where
`the cellular wireless system has multiple of sectors. The
`method can involve the functions of (i) determining that a
`mobile station is located in a given sector, (ii) establishing
`a PI-based location to represent the given sector, and (iii)
`communicating the PI-based location as a representation of
`where the mobile station is located.
`The function of establishing the PI-based location for the
`sector could take various forms. For example, it could be
`simply querying a table or other data source that correlates
`an already-created PI-based location with the sector. As
`another example, it could extend to creating the PI-based
`location for the sector, including establishing a polygon of
`influence for the sector.
`The function of communicating the PI-based location can
`also take various forms. For example, it can involve storing
`the PI-based location in a data store that is accessible (e.g.,
`through suitable messaging) to a recipient entity Such as a
`mobile positioning center and/or a location-based-service
`provider for instance. As another example, it can involve
`transmitting the PI-based location to a location-based ser
`Vice provider in response to a request for a location of the
`mobile station.
`In still another respect, an exemplary embodiment of the
`invention can take the form of a method that involves the
`functions of (i) determining that a mobile station is located
`in a given sector of a cellular wireless system, (ii) selecting
`a PI-based location to represent the given sector and (iii)
`performing a service based on the PI-based location.
`In yet another respect, an exemplary embodiment of the
`invention can take the form of a system for communicating
`mobile station location in a cellular wireless system having
`a number of sectors, where the mobile station is operating in
`one of the sectors. The system can include a processor, a data
`storage medium, and a set of machine language instructions
`stored in the data storage medium and executable by the
`processor to establish a PI-based location respectively for
`each sector. Further, the system can be programmed to
`communicate that PI-based location to a recipient entity, so
`as to facilitate a location-based service.
`These as well as other aspects and advantages of the
`present invention will become apparent to those of ordinary
`skill in the art by reading the following detailed description,
`with appropriate reference to the accompanying drawings.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,072,666 B1
`
`5
`
`10
`
`15
`
`25
`
`30
`
`35
`
`4
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`An exemplary embodiment of the present invention is
`described herein with reference to the drawings, in which:
`FIGS. 1 and 3–11 illustrate a process of creating PI-based
`locations for the sectors in an exemplary coverage area;
`FIG. 2 illustrates exemplary radiation patterns from a base
`station; and
`FIG. 12 is a simplified block diagram illustrating a
`network arrangement Suitable for carrying out the exemplary
`embodiment.
`
`DETAILED DESCRIPTION OF EXEMPLARY
`EMBODIMENT
`
`1. Characterizing Sectors
`In accordance with an exemplary embodiment of the
`present invention, a cellular wireless carrier or other entity
`will establish a respective “polygon-of-influence based loca
`tion” (“PI-based location') to represent each of one or more
`sectors in a given cellular coverage area. Generally speak
`ing, a PI-based location for a given sector can be defined as
`a location that is based on a polygon of influence for that
`sector taken with respect to one or more other sectors.
`A polygon of influence for a sector taken with respect to
`other sectors is a polygon in which Substantially all points
`are closer to the origin of the sector than to the origins of the
`other sectors. As such, a PI-based location for a given sector
`can be a geographic characterization of the polygon of
`influence itself (such as the geographic coordinates of the
`nodes of the polygon), or of an area drawn with respect to
`the polygon of influence.
`Alternatively, the PI-based location can be geographic
`coordinates of one or more points within the polygon, Such
`as Substantial midpoint of the polygon or of a minimum
`bounding rectangle drawn around the polygon. Still alter
`natively, the PI-based location can take other forms, based in
`Some way on a polygon of influence. For instance, a PI
`based location can be a street address or intersection that lies
`at or near the center of a polygon of influence. Other
`examples are possible as well.
`Numerous techniques and tools may be applied in order to
`establish polygons of influence for the sectors in a coverage
`area. The process may be executed manually, Such as by
`plotting the locations of base stations and drawing lines to
`form the polygons. Alternatively, the process may be auto
`mated, such as by programming a computer with instruc
`tions to read data points representing the locations of base
`stations, to “draw the polygons in memory, and to output
`(e.g., print and/or display) indications of the polygons. Still
`alternatively, the process may be a combination of manual
`and automated techniques.
`In accordance with the exemplary embodiment, the pro
`cess will be largely computer-executed. The input to the
`process can be a data table that lists as records the location
`coordinates (e.g., latitude/longitude) and azimuth (e.g.,
`angle of propagation from true north) of each sector in the
`coverage area. Since most base stations will include three
`120° antennas (to achieve approximately 360° coverage),
`the input data table will likely (although not necessarily) list
`the same base station coordinates for each sector of a given
`base station, although each of the three sectors will likely
`have a different azimuth.
`The output of the process, in turn, may be a revised data
`table that reflects representative coordinates of each sector in
`the coverage area, established according to the exemplary
`
`Page 11 of 19
`
`

`

`5
`embodiment. This output table may then be used as a basis
`to characterize the location of a mobile station that is
`operating in a given sector. Namely, the mobile station may
`be said to be operating at or near the representative coordi
`nates of the sector. Another output of the process may be a
`number of objects (object models in computer memory) that
`define polygons of influence derived for the sectors in the
`coverage area. A carrier can then conveniently use these
`objects to display and/or report the polygons of influence.
`Referring to FIG. 1, a schematic illustration of a cellular
`coverage area 10 is provided, to help explain how the
`exemplary embodiment will operate in practice. For sim
`plicity, coverage area 10 is shown to include five represen
`tative base station towers, designated A, B, C, D and E. In
`reality, the coverage may have more or fewer base station
`towers. Further, the coverage area is shown to include an
`outer boundary 12.
`Further for simplicity, it will be assumed that each base
`station tower employs three antennas (or antenna arrange
`ments) to produce three evenly spaced 120° radiation pat
`terns representing respective 120° sectors. FIG. 2 schemati
`cally depicts (in an idealized form) Such radiation patterns
`14, 16, 18 (i.e., sectors 14, 16, 18) extending from exem
`plary base station tower A of FIG. 1. Each antenna, and
`therefore each respective radiation pattern, has a respective
`azimuth, which is its angle of propagation from true north or
`from some other reference direction. FIG. 2 shows an
`azimuth 0 for sector 18 by way of example. It should be
`understood that other radiation patterns are possible as well.
`According to an exemplary embodiment, the process of
`30
`deriving polygons of influence for the sectors in a coverage
`area involves first distinguishing the point of origin (or
`"origin point) of each sector for a given base station, and
`then drawing a polygon of influence for each sector. The
`reason to distinguish the point of origin of each sector is to
`enable a polygon of influence algorithm to readily divide
`apart the sectors of a given base station, as will become more
`apparent from the following discussion.
`To distinguish the point of origin of each sector for a
`given base station, a computer can be programmed to plot
`for each sector a point that extends radially for about 3 feet
`(or Some other relatively small distance, the same for each
`sector) from the base station, along the azimuth of the sector.
`Assuming that the input data table lists the same base station
`coordinates for each of its sectors, this distinguishing
`process can thus involve looking at each record in the input
`table and shifting the sector coordinates by 3 feet along the
`azimuth indicated in the record. This will usually be a
`reasonable approximation in any event, since the three
`antennas on a base station tower usually extend out several
`feet along their azimuths from the tower.
`One way to do this is to apply a computer program written
`to use the spatial capabilities of a software product such as
`MapInfo (available from MapInfo Corporation of Troy,
`N.Y.). The program can be instructed to read a data point
`(latitude/longitude coordinates) and azimuth from each
`record of a table. For each record, the program can then be
`instructed to (i) draw a circle of 3 foot radius around the data
`point, (ii) draw a line of greater than 3 foot length extending
`at the azimuth, and then (iii) find the point of intersection
`between the circle and line. The program can then be
`instructed to output that point as the distinguishing point of
`origin of the sector.
`FIG. 3 illustrates this process for the sectors of base
`station. A for instance. In the exemplary embodiment, the
`input data table would list the geographic coordinates of
`base station tower A as being the location of this sector. A
`
`50
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`US 7,072,666 B1
`
`10
`
`15
`
`25
`
`6
`circle 20 of radius 3-feet can then be drawn (i.e., its equation
`established) around that location. For sector 18, a line 22 can
`then be drawn extending from the location out at the azimuth
`0 of the sector. Circle 20 and line 22 will then intersect at a
`point A1, the geographic coordinates of which can be used
`as the point of origin of the sector. This same process can be
`repeated for each sector in a coverage area, thereby produc
`ing three points around each base station tower, representing
`the points of origin of the three sectors established by the
`base station.
`Turning now to FIG. 4, coverage area 10 is shown with
`the resulting points of origin indicated for each of the three
`sectors of each base station A-E. The points of origin of the
`sectors established by base station A are shown as A1, A2
`and A3, the points of origin of the sectors established by base
`station B are shown as B1, B2 and B3, and so forth.
`Provided with a point of origin of each sector in the
`coverage area, the points can be input into a computer
`program that is executable to establish a polygon of influ
`ence for each point with respect to the other points in the
`coverage area (a “PI program.) Before applying the PI
`program, however, it would be best to first simplify the
`boundaries of the coverage area. In particular, according to
`the exemplary embodiment, a minimum bounding rectangle
`(“MBR) can be established around the outer boundary 11 of
`the coverage area. Assuming that outer boundary is modeled
`as a bounding polygon defined by a number of nodes having
`x, y coordinates, the MBR can extend from the minimum X,
`y coordinates of the bounding polygon to the maximum X,
`y coordinates of the bounding polygon. (After applying the
`PI program, the bounding polygon can then be used to clip
`any polygons of interest that extend beyond it.)
`FIG. 5 illustrates such an MBR 26 drawn around coverage
`area 10 of FIG. 1. In this figure, the outer boundary 11 of
`coverage area 10 has been then omitted for clarity. Further,
`the original base station locations have been omitted for
`clarity as well. The end result is an MBR encompassing the
`points of origin of each sector in coverage area 10.
`Provided with the MBR encompassing a set of points of
`origin, the PI program will then proceed to derive a polygon
`of influence for each point. To do so, an exemplary PI
`program will be written to execute the following process for
`each point in the set (i.e., for each sector as to which the
`program is instructed to establish a polygon of influence):
`(1) Make a list of all connecting-lines that connect the
`point to each of the other points in the set.
`(2) Make a list of lines to use as potential PI edges,
`including:
`(a) Perpendicular bisectors of each connecting-line;
`and
`(b) The edges of the MBR.
`(3) Clip all of the potential PI edge lines where they
`intersect each other. For each potential PI edge line,
`retain as a PI edge the piece of the PI edge line that is
`closest to the point. The process of clipping is com
`pleted once the potential PI edge lines do not intersect
`any previously clipped line segment in the clipped PI
`edge list.
`(4) Connect all of the PI edges, so as to form a polygon
`that completely encloses the point.
`FIGS. 6-11 illustrate this process in detail for exemplary
`point A1 in FIG. 5, so as to establish a polygon of influence
`for the corresponding sector 18 of base station A.
`As noted, the exemplary PI program first makes a list of
`all connecting-lines that connect points to each other in the
`set. FIG. 6 illustrates these connecting-lines for point A1.
`
`Page 12 of 19
`
`

`

`US 7,072,666 B1
`
`7
`Each line radiates from point A1 to another point in the set.
`For example, a connecting-line 28 extends from point A1 to
`point C3.
`Next, the PI program makes a list of potential PI edge
`lines, including (a) perpendicular bisectors of each connect- 5
`ing-line and (b) the edges of the MBR. FIG. 7 depicts an
`exemplary perpendicular bisector 30 of line 28. In turn, FIG.
`8 depicts perpendicular bisectors of all of the connecting
`lines within the MBR.
`In turn, the PI program clips all of the potential PI edge 10
`lines where they intersect each other. As shown in FIGS. 9
`and 10, the result of this clipping for point A1 is a polygon
`of influence 32, which the PI program can represent by the
`coordinates of nodes 32a, 32b, 32c, 32d and 32e. In the
`exemplary embodiment, substantially every point within this 15
`polygon of influence will be closer to point A1 than to other
`points within the MBR.
`Note that when the PI program performs step (2)(a) of this
`process, it will inherently include as potential PI edge lines
`the lines that divide the sectors of a given base station. The 20
`reason for this is that a perpendicular bisector of a line that
`connects two sector points of origin derived with the process
`above will itself extend radially from the base station,
`directly between the azimuths of the two sectors. This
`should generally be the case regardless of whether the 25
`sectors all provide 120° coverage.
`As output for each sector, the PI program can provide a
`list of the nodes of the polygon derived for the sector. These
`nodes can then be provided as input to the MapInfo program,
`So as to allow the MapInfo program to represent each 30
`polygon as an object, which can be displayed or manipulated
`as desired.
`As noted above, the original bounding polygon can be
`used to clip the polygons produced by the PI program. To do
`this, the nodes of the original bounding polygon can be input 35
`to the MapInfo program, so that the MapInfo program can
`represent the bounding polygon as an object. Provided with
`an object representing each polygon of influence and an
`object representing the original bounding polygon, the Map
`Info program can readily clip each polygon of influence to 40
`the extent it extends beyond the bounding polygon. The
`MapInfo program can then output a revised set of nodes for
`the polygons of influence.
`The process described so far for establishing polygons of
`influence for the sectors in a coverage area is intended to be 45
`an example only. Variations are possible. For instance, one
`variation may be to omit the function of distinguishing the
`points of origin of each sector for a given base station.
`Instead, the PI program can receive as input the coordinates
`of each base station (which is typically, in effect, the point 50
`of origin for all sectors of the base station) and can generate
`as output a polygon of influence around each base station. In
`turn, for each base station that defines N sectors of specified
`azimuths, the PI program or another program can divide
`each polygon of influence into N parts. For instance, a 55
`program can draw lines extending radially from the base
`station directly in between each azimuth, and the program
`can clip the lines at the point that they intersect the polygon
`of influence. The point of intersection can then function as
`a common node of each adjacent sector of the base station. 60
`Other variations are possible as well.
`As noted above, the polygon of influence derived for a
`given sector may then be used as a basis to characterize the
`location (e.g., the geographic scope or position) of the sector
`and thereby as a basis to characterize the location a mobile 65
`station known to be operating in the sector. This should
`function as good characterization, because every point in the
`
`8
`polygon of influence for a sector is likely (if not certain) to
`be closer to the base station that defines the sector than to
`any other base station in the coverage area. Phrased another
`way, when a mobile station is operating in a given sector, the
`mobile station is likely to be located in the polygon of
`influence for the sector. (Note that, depending on various
`factors (e.g., signal strength, topography, etc.), this assump
`tion may sometimes fail; but it is believed that the assump
`tion will be valid in most cases. Nevertheless, the present
`invention functions to estimate location, which may be more
`or less accurate from case to case.)
`In the exemplary embodiment, the PI program can con
`veniently be written to record in the output data table a
`PI-based location respectively for each sector in a coverage
`area. The PI-based location for a given sector can take
`various forms. As an example, the PI-based location can be
`a list of the geographic coordinates of the nodes that define
`the polygon of influence for the sector. Conveniently, a
`recipient of Such an indication could model the polygon of
`influence (using the MapInfo program, for instance) and
`perhaps display the polygon on a map, so as to clearly
`understand where the polygon of influence lies and thus
`where the mobile station is likely positioned. This form of
`indication would be particularly useful for emergency Ser
`vices, since it would allow emergency service personnel to
`quickly visualize the area where a mobile 911 caller is likely
`to be located.
`As another example, the PI-based location for each sector
`can instead take the form of a representative point selected
`from within the polygon of influence. One Such representa
`tive point could be the centroid, or center of mass, of the
`polygon. Typical polygons of influence that will result from
`the process described above, however, will be complex,
`having five or more sides, and it is computationally difficult
`to determine the center of mass of a complex polygon.
`Therefore, instead of using the center of mass as the repre
`sentative point, a more simple representative point can be
`used.
`One example of a more simple representative point is the
`midpoint of a minimum bounding rectangle around the
`polygon of influence, i.e., the midpoint of a rectangle
`extending from the minimum X and y coordinates of the
`polygon of influence to the maximum X and y coordinates of
`the polygon of influence. In the exemplary embodiment, the
`PI program can conveniently be written to find the mid-point
`of Such a rectangle by finding the intersection between the
`diagonals of the rectangle.
`Referring to FIG. 11, for example, a minimum bounding
`rectangle 34 has been drawn around polygon of influence 32,
`and diagonal lines 36,38 have been drawn through rectangle
`34. Those diagonal lines intersect at a point 40. With this
`exemplary process, the geographic coordinates of point 40
`can be used as the PI-based location representing sector 18
`of base station A. Other examples are possible as