Patent Description:
The present inventive concept relates generally to networks, more particularly, to networks including smart devices and systems and methods for communicating with out of range devices therein.

Smart meters and sensors communicate over a network, for example, the FlexNet® communication network. The network allows secure transmission and reception of data, for example, customer usage data. This data can be used to proactively manage electric, water and gas systems. The two-way network enables data to be collected, delivered, managed and analyzed in real time and as often as possible.

The networks are constantly updating the devices (endpoints) that communicate within the network. As used herein an "endpoint", refers to any non-transceiver tower device operating in the network, for example, any type of smart meter, gas, heat or electric. When an endpoint that is out of range of a transceiver, hereinafter, an out of range device (ORD), it communicates through another endpoint, or buddy device. The buddy device (non-ORD) may be a peer device or may be a device configured to receive and/or relay a transmission.

Buddy devices (non-ORDs) are generally discovered within the network for each ORD. Currently, a search algorithm may be applied to the set of endpoints comprising a network in an attempt to identify candidate (possible) buddy devices (endpoints) for all out of range devices (ORDs) in the system. Thus, as illustrated in <FIG>, all endpoints (non-ORDs) within a radius R from the target endpoint X (ORD) are located in each of the areas A, B, C and D. The radius R can be any distance set by the operator, for example, one (<NUM>) mile. The endpoints in area A may be ignored in some scenarios as they are deemed too close to the target X to provide anything additional. The endpoints in each area A, B, C and D having the strongest signals, or signals over a particular threshold, are identified out to the radius R. Thus, currently searching for non-ORDs within a configurable radius R of the ORD (X) requires computing a distance from every identified ORD to every non-ORD. Storing the distances generally requires O (n<NUM>) space (where n is the number of endpoints in the network). These distances are computed each time and takes about O(n<NUM>) time. For a large input data set, for example, four million endpoints, this process required may take approximately two full days to complete. An improved method of locating non-ORDs in a network is desired.

<CIT> discloses a communication system for supporting machine type communication within a cellular communication network.

<CIT> discusses the use of Machine-to-machine devices to enable the automatic collection of fingerprint data without human intervention at various locations in a wireless communication system.

<NPL> addresses the design and development of an optimal Wide Area Monitoring, Protection and Control architecture, communication infrastructure and real-time applications for a role in future power network operation and understanding.

<NPL> analyzes and compares two relaying schemes for uplink in the context of cellular systems: Simple relaying, where a user is served either by a relay node or the base station; and Cooperative Relaying, where a user is served by the relay node, the base station or both in a cooperative manner.

The present invention provides a method for identifying in range endpoints in a network according to claim <NUM>, a corresponding computer program in line with claim <NUM> and a system for identifying in range endpoints in a network as defined by claim <NUM>. The method includes providing a map including endpoints in the network, the endpoints including target endpoints, out of range endpoints and non-out of range endpoints; positioning a grid over the map including the endpoints in the network, the grid including a plurality of subsections each having a defined radius, locating a target endpoint on the map and in one of the subsections of the grid; and identifying a plurality of endpoints within subsections of the grid within a defined range of the target endpoint.

Each of the plurality of subsections are hexagons. Identifying the plurality of endpoints further includes identifying the plurality of endpoints within the hexagons within the defined range of the target endpoint. In certain embodiments, the defined radius may be about <NUM> meters and the defined range may be two times the defined radius or <NUM> meters.

In still further embodiments, providing the map may include using a projection program to project endpoints onto a map using latitude and longitude coordinates associated with each of the endpoints, and the map including the endpoints may be stored. In certain embodiments, the map including the endpoints in the network may be periodically regenerated using the projection program to provide an updated map and the updated map may be stored.

In some embodiments, the defined range may be a multiple of the defined radius.

In further embodiments, the endpoints in the network may be any non-transceiver tower device operating in the network. For example, the endpoints in the network may be smart devices, such as smart meters.

Related system and computer program product claims are also provided herein.

The present inventive concept will be described more fully hereinafter with reference to the accompanying figures, in which embodiments of the inventive concept are shown. This inventive concept may, however, be embodied in many alternate forms and should not be construed as limited to the embodiments set forth herein.

Accordingly, specific embodiments thereof are shown by way of example only in the drawings and will herein be described in detail. Like numbers refer to like elements throughout the description of the figures.

It will be further understood that the terms "comprises", "comprising," "includes" and/or "including" when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. Moreover, when an element is referred to as being "responsive" or "connected" to another element, it can be directly responsive or connected to the other element, or-intervening elements may be present. In contrast, when an element is referred to as being "directly responsive" or "directly connected" to another element, there are no intervening elements present.

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this inventive concept belongs.

For example, a first element could be termed a second element, and, similarly, a second element could be termed a first element without departing from the teachings of the disclosure.

As used herein an "endpoint", refers to any non-transceiver tower device operating in the network, for example, any type of smart meter, gas, heat or electric. When an endpoint that is out of range of a transceiver, hereinafter, an out of range device (ORD), it communicates through another endpoint, or buddy device. The buddy device (non-ORD) may be a peer device or may be a device configured to receive and/or relay a transmission. As further used herein, "n" refers to the number of endpoints in the network.

As discussed above, improved methods for identifying non-ORDs within a specified radius R of an ORD are needed. Currently, the length of time it takes to identify the non-ORDs using conventional methods is extremely long. Accordingly, embodiments of the present inventive concept provide methods and systems for reducing the amount of time spent locating the non-ORD endpoints in a network. In particular, some embodiments of the present inventive concept reduce the search space for endpoints (non-ORDs) that are "nearby" (within a particular radius) of a particular other endpoint (ORD). As will be discussed further below with respect to <FIG>, embodiments of the present inventive concept project geospatial coordinates from a latitude and longitude on to a hexagonal grid. A first order approximation of distance can be made based on the size of the hexagons chosen. The size of the hexagon is arbitrary and, therefore, customizable, but is fixed once it is chosen. Embodiments of the present inventive concept reduce the time complexity of the "nearby" search from O(n<NUM>) to O(n log n), and the actual time from two days to about <NUM> minutes for <NUM> million endpoints.

It will be understood that the estimated time changes based on the number of endpoints included in the process. It will be further understood that although embodiments of the present inventive concept are discussed with respect to ORDs and non-ORDs (buddy devices), embodiments of the present inventive concept are not limited to this configuration. For example, embodiments of the present inventive concept may be used to determine presence of any type of endpoints without departing from the scope of the present inventive concept.

Embodiments of the present inventive concept are discussed herein using "big O" notation. For example, as discussed above, embodiments of the present inventive concept reduce the time complexity of the "nearby" search from O(n<NUM>) to O(n log n), and the actual time from two days to about <NUM> minutes for <NUM> million endpoints. The "big O" notation is used to-describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. In other words, "big O" is a theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items (endpoints). Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

Referring now to <FIG>, a hexagon grid generated in accordance with some embodiments of the present inventive concept will be discussed. First, a projection program, such as Web Mercator, is used to project the endpoints on a map using latitude and longitude coordinates of the endpoints. Then, the resulting projection created using the projection program is projected onto a hexagonal grid <NUM> as illustrated in <FIG>. In other words, the positions of the various endpoints, for example, ORDs and non-ORDS, are projected onto a map using a projection program and then a hexagonal grid can be positioned (superimposed) over the projection. In some embodiments, the hexagons have a radius R of about <NUM> meters, thus, 2R being <NUM> meters, which is approximately <NUM> mile. It will be understood that the radius R can be chosen to be any distance without departing from the scope of the present inventive concept.

Projecting every endpoint into its corresponding hexagon can be done in O(n) time. Since the positions of the endpoint are generally static, the projection is computed once and stored-in O(n) space for use. It is understood that endpoints can be added or removed from a network at any time. Thus, the projection may be recalculated periodically and restored to make sure the most up to date projection is being used.

Using the stored projections and the hexagonal grid, instead of using O(n<NUM>) time to choose candidate buddy devices for an ORD by searching all non-ORDs, the time can be reduced to about O(n log n) by searching only the hexagon containing the particular ORD you are interested in plus the ring of hexagons surrounding it. Using the hexagon in which the ORD sits and the surrounding hexagons allows a grid with a radius of one (<NUM>) mile to be covered if the radius R of the hexagon is <NUM> meters. As discussed above, the radius R is configurable and, therefore, not limited to a mile or <NUM> meters. Some embodiments of the present inventive concept are configured to compute the number of surrounding rings of hexagons needed to cover the particular distance chosen.

It will be understood that although embodiments of the present inventive concept are discussed herein as including a grid having a plurality of hexagonal subsections, embodiments of the present inventive concept are not limited to this configuration. The subsections of the grid may have any shape that lends itself to embodiments discussed herein without departing from the scope of the present inventive concept.

Referring now to <FIG>, an example of using a hexagon grid in accordance with some embodiments of the present inventive concept will be discussed. As illustrated in <FIG>, a projection includes a-series of possible buddy devices (endpoints) Y (non-ORDs) and a target endpoint X (ORD) and this projection is saved. A buddy device (non-ORD) may be a peer device or may be a device configured to receive and/or relay a transmission. Any two-way device in the wireless network may be capable of autonomously acting as a buddy device while carrying out its normal sensing functions.

Referring again to <FIG>, the hexagonal grid <NUM> is overlaid on the stored projection such that the target endpoint X is within a hexagon. Although the target endpoint X is illustrated as being in the center of the hexagon in <FIG>, it will be understood that the target endpoint X does not have to be in the center of a hexagon on the grid <NUM>. The hexagon in which the target endpoint X sits and the surrounding hexagons will be used to locate candidate buddies Y for the endpoint X. The relevant hexagons in <FIG> are shaded. Thus, the endpoints Y (non-ORDs) in each of the shaded hexagons are possible candidate buddies in accordance with embodiments discussed herein.

In some embodiments, rather than visiting every endpoint Y (ORD) within a given hexagon, coverage may be approximated as if all endpoints Y (ORDs) are located at a center of the hexagon. Candidate buddies may be chosen based on the approximated information. In these embodiments, time may be reduced to approximately O(log n) while still covering all endpoints Y (ORDs). However, there may be a tradeoff of reduced quality of the ORD to buddy path.

Referring now to <FIG>, a block diagram of an example network including ORDs and non-ORDs in accordance with embodiments discussed herein will be discussed. As illustrated in <FIG>, the network <NUM> includes transceiver towers T1 and TN, candidate buddy devices Y1, Y2, Y3 and YN and an ORD X. It will be understood that there may be more or less transceivers, candidate buddy devices and ORDs than illustrated in <FIG> without departing from the scope of the present inventive concept.

As shown in <FIG>, an ORD sends a message that is received by one or more buddies (Y1-YN) which are <NUM>-way endpoints. The <NUM>-way endpoints, re-transmit the ORD's message to a transceiver, a collector tower or other collector T1-TN. Thus, the ORD can use the non-ORDs (buddies) to communicate with the transceiver towers. Embodiments of the present inventive concept allow identification of non-ORDs for each ORD extremely efficient using a hexagon grid as briefly discussed above.

Referring now to <FIG>, a flowchart illustrating operations identifying in range endpoints in a network will be discussed. As illustrated in <FIG>, operations begin at block <NUM> by providing a map including endpoints in the network. The endpoints may include target endpoints, out of range endpoints and non-out of range endpoints. In some embodiments, providing the map includes using a projection program to project endpoints onto a map using latitude and longitude coordinates associated with each of the endpoints and storing the map including the endpoints. Since endpoints are constantly being added and removed from the network, the map may be periodically regenerated including the endpoints in the network using the projection program to provide an updated map and the updated map may be stored.

Endpoints in the network may include any non-transceiver tower device operating in the network. In some embodiments, endpoints in the network are smart devices, for example, smart meters.

Operations continue at block <NUM> by positioning a grid over the map including the endpoints in the network and a target endpoint is located on the map and in one of the subsections of the grid (block <NUM>). The grid includes a plurality of subsections each having a defined radius. In some embodiments, each of the plurality of subsections are hexagons as discussed above. Thus, the plurality of endpoints may be identified by locating endpoints within the hexagons within the defined range of the target endpoint. In some embodiments, the defined radius may be about <NUM> meters the defined range may two times the defined radius or <NUM> meters. However, it will be understood that embodiments of the present inventive concept are not limited to this configuration.

A plurality of endpoints may be defined within subsections of the grid within a defined range of the target endpoint (block <NUM>). In other- words, as discussed above, in embodiments having hexagon shaped subsections, all endpoints within a subsection within two times the radius of the subsection are identified as in range endpoints for use in transmission to and from the target device.

Although embodiments of the present inventive concept are discussed above with respect to a buddy-ORD communication model, embodiments of the present inventive concept are not limited to this configuration. For example, embodiments of the present inventive concept may be used in combination with other types of networks, such as a mesh network. In other words, rather than ORDs and non-ORDs, embodiments discussed herein could be generalized to choose either a first-hop candidate or the next-hop candidate rather than a buddy candidate.

As illustrated in <FIG>, a hop is a computer networking term that refers to the number of other devices, for example, routers that a packet passes through from its source device <NUM> (workstation <NUM>) to its destination device <NUM> (workstation <NUM>). In some embodiments, a "hop" is counted when a packet passes through other hardware on a network (besides routers <NUM> and <NUM>), like switches, access points, repeaters and the like. In <FIG>, the packet traverses two hops (two routers) before reaching its destination <NUM>, workstation <NUM>.

Applying embodiments discussed here to a network similar to the network of <FIG>, using the mesh network example, one or more devices in the hexagon may be chosen to act as a "hub" for the other devices (the first-hop variant), and the hub may be responsible for relaying to adjacent hexagons. The next hop would be to an endpoint in a hexagon closer to the intended destination.

As discussed above, embodiments of the present inventive concept a projection program is used to project endpoints on a map, which is used to create the hexagonal grid. Thus, some sort of data processing is needed to create and store the data. <FIG> is a block diagram of an example of a data processing system <NUM> suitable for use in the systems in accordance with embodiments of the present inventive concept. The data processing may take place in any of the devices (or all of the devices) in the system without departing from the scope of the present inventive concept. As illustrated in <FIG>, the data processing system <NUM> includes a user interface <NUM> such as a keyboard, keypad, touchpad, voice activation circuit or the like, I/O data ports <NUM> and a memory <NUM> that communicates with a processor <NUM>. The I/O data ports <NUM> can be used to transfer information between the data processing system <NUM> and another computer system or a network. These components may be conventional-components, such as those used in many conventional data processing systems, which may be configured to operate as described herein.

As will be appreciated by one of skill in the art, embodiments of the present inventive concept may be embodied as a method, system, data processing system, or computer program product. Accordingly, the present inventive concept may take the form of an embodiment combining software and hardware aspects, all generally referred to herein as a "circuit" or "module. " Furthermore, the present inventive concept may take the form of a computer program product on a non-transitory computer usable storage medium having computer usable program code embodied in the medium. Any suitable computer readable medium may be utilized including hard disks, CD ROMs, optical storage devices, or other electronic storage devices.

Computer program code for carrying out operations of the present inventive concept may be written in an object oriented programming language such as Matlab, Mathematica, Java, Smalltalk, C or C++. However, the computer program code for carrying out operations of the present inventive concept may also be written in conventional procedural programming languages, such as the "C" programming language or in a visually oriented programming environment, such as Visual Basic.

Certain of the program code may execute entirely on one or more of a user's computer, partly on the user's computer, as a standalone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer.

The inventive concept is described in part with reference to flowchart illustrations and/or block diagrams of methods, devices, systems, computer program products and data and/or system architecture structures according to embodiments of the inventive concept. It will be understood that each block of the illustrations, and/or combinations of blocks, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general-purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified-in the block or blocks.

These computer program instructions may also be stored in a computer readable memory or storage that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory or storage produce an article of manufacture including instruction means which implement the function/act specified in the block or blocks.

The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions/acts specified in the block or blocks.

Claim 1:
A method for identifying in range endpoints in a network, the method comprising:
providing a map including endpoints in the network;
positioning a hexagonal grid (<NUM>) over the map including the endpoints in the network, the hexagonal grid including a plurality of hexagonal subsections each having a defined radius, R,
determining a target endpoint and a destination endpoint, the target endpoint being in one of the hexagonal subsections of the grid and being out of range of the destination endpoint;
identifying a plurality of non-out of range endpoints within subsections of the hexagonal grid within a defined range of the target endpoint on the map, the plurality of non-out of range endpoints being within range of the destination endpoint, and
selecting one of the identified non-out of range endpoints to communicate messages between the target endpoint that is out of range of the destination endpoint and the destination endpoint by receiving the messages at the selected non-out of range endpoint and retransmitting the messages to the target endpoint or the destination endpoint,
wherein the providing, positioning, determining, identifying and selecting are performed by at least one processor.