(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY(PCT)
`
`
`
`(19) World Intellectual Property Organization
`International Burcau
`
`(43) International Publication Date
`28 May 2009 (28.05.2009)
`
`(51) International Patent Classification:
`GO8C 19/00 (2006.01)
`
`(21) International Application Number:
`PCT/US2008/013019
`
`(22) International Filing Date:
`21 November 2008 (21.11.2008)
`
`(25) Filing Language:
`
`(26) Publication Language:
`
`English
`
`English
`
`(30) Priority Data:
`60/989,957
`60/989,967
`60/989,958
`60/989,964
`60/989,950
`60/989,953
`60/989,975
`60/989,959
`60/989,961
`60/989,962
`60/989,95 1
`60/989,955
`60/989,952
`60/989,954
`60/992,312
`
`
`
`25
`November 2007 (25.11.2007)
`25
`November2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November 2007 (25.11.2007)
`25
`November2007 (25.11.2007)
`4 December 2007 (04.12.2007)
`
`qeaaaqcncacqcqcaqaqaqqqqadcd
`
`
`AANAANANNNADNANAA
`
`(10) International Publication Number
`WO 2009/067251 Al
`
`60/992,313
`60/992,315
`61/025,279
`61/025,270
`61/025,276
`61/025,282
`61/025,271
`61/025,287
`61/025,278
`61/025,273
`61/025,277
`61/094,116
`
`4 December 2007 (04.12.2007)
`4 December 2007 (04.12.2007)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`31 January 2008 (31.01.2008)
`4 September 2008 (04.09.2008)
`
`US
`US
`US
`US
`US
`US
`US
`US
`US
`US
`US
`US
`
`(71)
`
`(72)
`(75)
`
`(74)
`
`(81)
`
`Applicant (for all designated States except US): TRIL-
`LIANT NETWORKS,INC. [US/US]; 1300 Island Drive,
`Suite 103, Redwood City, CA 94065 (US).
`
`Inventor; and
`Inventor/Applicant (for US only): VEILLETTE,Michel
`[CA/CA]; 109 des Flandres, Watcrloo, Québec JOE 2NO
`(CA).
`
`Agent: BEY, Dawn-Marie; King & Spalding, LLP, 1700
`Pennsylvania Avenue, N.W., Suite 200, Washington, DC
`20006 (US).
`
`Designated States (unless otherwise indicated, for every
`kind of national protection available): AE, AG, AL, AM,
`AO,AT, AU, AZ, BA, BB, BG, BH, BR, BW, BY, BZ, CA,
`
`[Continued on next page]
`
`(54) Titles COMMUNICATION AND MESSAGE ROUTE OPTIMIZATION AND MESSAGING IN A MESH NETWORK
`
`POONNL _
`7~~s,/MESH NETWORK AY
`100
`
`*s
`
`«
`
`" response |
`— MESH GATE A
`message,
`102
`
`FIG 1A
`
`
`
`WIDE AREA
`NETWORK
`416
`
`\
`
`!
`
`12
`
`1
`1
`\
`{
`
`ey
`'
`,
`124 i
`tt
`
`
`
`
`
`
`
`message fesponse
`
`METER D
`
`
`4110
`
`
`METER G
`108
`
`
`
`
`
`
`
`
`METER B
`106
`
`
`
`
`
`
`
`\
`
`METER A
`104
`
`
`
`
`
`~ 4
`
`\
`
`‘
`A“
`NY
`SLU Ne Ne
`
`n
`f
`
`(57) Abstract: A method and system facilitate communications between an unassociated device and a server via a mesh network
`and a wide arca network. The method may include recciving transmissions from candidate proxy devices, wherein cach candidate
`proxy device is associated with a mesh network. The method may include selecting a proxy device from the candidate proxy devices.
`The method may include communicating with a server via the proxy device and the associated mesh network.
`
`
`
`
`
`WO2009/067251AdITNVRINMINENATATINNINAITUMAATAA
`
`

`

`WO 2009/067251 Al
`
`CH, CN, CO, CR, CU, CZ, DE, DK, DM, DO, DZ, EC, EE,
`EG,ES, FI, GB, GD, GE, GH, GM, GT, HN, HR, HU,ID,
`IL,IN,IS, JP, KE, KG, KM, KN, KP, KR, KZ, LA, LC, Lk,
`LR, LS, LT, LU, LY, MA, MD, ME, MG, MK, MN, Mw,
`Mx, MY, MZ, NA, NG, NI, NO, NZ, OM,PG, PH,PL, PT,
`RO, RS, RU, SC, SD, SE, SG, SK, SL, SM,ST, SV, SY, TJ,
`TM,TN,TR,TT, TZ, UA, UG, US, UZ, VC, VN, ZA, ZM,
`ZW.
`
`(84)
`
`Designated States (unless otherwise indicated, for every
`kind of regional protection available): ARIPO (BW, GH,
`GM, KE, LS, MW, MZ, NA, SD, SL, SZ, TZ, UG, ZM,
`
`ZW), Eurasian (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM),
`European (AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI,
`FR, GB, GR, HR, HU,IE,IS, IT, LT, LU, LV, MC, MT, NL,
`NO,PL, PT, RO, SE, SI, SK, TR), OAPI (BF, BJ, CF, CG,
`CI, CM, GA, GN, GQ, GW, ML, MR, NE, SN, TD, TG).
`
`Published:
`
`with international search report
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`COMMUNICATION AND MESSAGE ROUTE OPTIMIZATION
`AND MESSAGINGIN A MESH NETWORK
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`[0001] This application claims the benefit of priority to the following United States
`
`provisional patent applications which are incorporated herein by reference in their entirety:
`
`serial number 60/989,957 entitled “Point-to-Point Communication within a Mesh
`Network", filed November 25, 2007 (TR0004-PRO);
`
`serial number 60/989,967 entitled “Efficient And Compact Transport Layer And Model
`
`For An Advanced Metering Infrastructure (AMI) Network,” filed November 25, 2007
`
`(TRO003-PRO);
`
`serial number 60/989,958 entitled “Creating And Managing A Mesh Network Including
`
`Network Association,” filed November 25, 2007 (TRO00S5-PRO);
`
`serial number 60/989,964 entitled “Route Optimization Within A Mesh Network,” filed
`
`November 25, 2007 (TRO007-PRO);
`
`serial number 60/989,950 entitled “Application Layer Device Agnostic Collector
`
`Utilizing ANSI C12.22,” filed November 25, 2007 (TROO09-PRO);
`
`serial number 60/989,953 entitled “System And Method For Real Time Event Report
`
`Generation Between Nodes And Head End Server In A Meter Reading Network
`
`Including From Smart And Dumb Meters,” filed November 25, 2007 (TR0010-PRO);
`
`serial number 60/989,975 entitled “System and Method for Network (Mesh) Layer And
`
`Application Layer Architecture And Processes,” filed November 25, 2007 (TROO14-
`
`PRO);
`
`°
`
`serial number 60/989,959 entitled “Tree Routing Within a Mesh Network,” filed
`
`November 25, 2007 (TR0017-PRO);
`
`serial number 60/989,961 entitled “Source Routing Within a Mesh Network,” filed
`
`November 25, 2007 (TRO019-PRO);
`
`serial number 60/989,962 entitled “Creating and Managing a Mesh Network,” filed
`
`November 25, 2007 (TRO020-PRO);
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`e
`
`serial number 60/989,951 entitled ‘““Network Node And Collector Architecture For
`
`Communicating Data And Method Of Communications,” filed November 25, 2007
`
`(TR0021-PRO);
`
`e
`
`serial number 60/989,955 entitled “System And Method For Recovering From Head
`
`End Data Loss And Data Collector Failure In An Automated Meter Reading
`
`Infrastructure,” filed November 25, 2007 (TR0022-PRO);
`
`e
`
`e
`
`serial number 60/989,952 entitled “System And Method For Assigning Checkpoints To
`A Plurality Of Network Nodes In Communication With A Device Agnostic Data
`
`Collector,” filed November 25, 2007 (TR0023-PRO);
`serial number 60/989,954 entitled “System And Method For Synchronizing Data In An
`Automated Meter Reading Infrastructure,” filed November 25, 2007 (TR0024-PRO);
`
`e
`
`serial number 60/992,312 entitled “Mesh Network Broadcast,” filed December 4, 2007
`
`(TRO027-PRO);
`
`e
`
`serial number 60/992,313 entitled "Multi Tree Mesh Networks", filed December 4,
`
`2007 (TR0O028-PRO);
`
`e
`
`serial number 60/992,315 entitled “Mesh Routing Within a Mesh Network,” filed
`
`December 4, 2007 (TR0029-PRO);
`
`e
`
`serial number 61/025,279 entitled "Point-to-Point Communication within a Mesh
`
`Network", filed January 31, 2008 (TR0030-PRO), and which are incorporated by
`
`reference.
`
`e
`
`serial number 61/025,270 entitled “Application Layer Device Agnostic Collector
`
`Utilizing Standardized Utility Metering Protocol Such As ANSI C12.22,” filed January
`
`31, 2008 (TR003 1-PRO);
`
`serial number 61/025,276 entitled “System And Method For Real-Time Event Report
`Generation Between Nodes And Head End Server In A Meter Reading Network
`
`Including Form Smart And Dumb Meters,”’ filed January 31, 2008 (TR0032-PRO);
`
`e
`
`serial number 61/025,282 entitled “Method And System for Creating And Managing
`Association And Balancing Of A Mesh Device In A Mesh Network,” filed January 31,
`
`2008 (TRO035-PRO);
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`serial number 61/025,271 entitled “Method And System for Creating And Managing
`Association And Balancing Of A Mesh Device In A Mesh Network,” filed January 31,
`
`2008 (TRO037-PRO);
`
`serial number6 1/025,287 entitled "System And Method For Operating Mesh Devices In
`
`Multi-Tree Overlapping Mesh Networks", filed January 31, 2008 (TRO038-PRO),;
`
`serial number 61/025,278 entitled “System And Method For Recovering From Head
`
`End Data Loss And Data Collector Failure In An Automated Meter Reading
`
`Infrastructure,” filed January 31, 2008 (TR0039-PRO);
`
`serial number 61/025,273 entitled “System And Method For Assigning Checkpoints to
`
`A Plurality Of Network Nodes In Communication With A Device-Agnostic Data
`
`Collector,”filed January 31, 2008 (TRO040-PRO);
`
`serial number 61/025,277 entitled “System And Method For Synchronizing Data In An
`
`Automated Meter Reading Infrastructure,” filed January 31, 2008 (TR0041-PRO), and
`
`serial number 61/094,116 entitled “Message Formats and Processes for Communication
`
`Across a Mesh Network,”filed September 4, 2008 (TRO049-PRO).
`
`[0002]
`
`This application hereby references and incorporates by reference each of the
`
`following United States patent applications filed contemporaneously herewith:
`
`serial number
`
`entitled "Point-to-Point Communication within a Mesh
`
`Network", filed November 21, 2008 (TRO004-US);
`
`serial number
`
`entitled “Efficient And Compact Transport Layer And
`
`Model For An Advanced Metering Infrastructure (AMI) Network,” filed November 21,
`
`2008 (TR0003-US);
`
`serial number
`
`entitled “COLLECTOR DEVICE AND SYSTEM
`
`UTILIZING STANDARDIZED UTILITY METERING PROTOCOL,”filed November
`
`21, 2008 (TROO009-US),
`
`serial number
`
`entitled “METHOD AND SYSTEM FOR CREATING
`
`AND MANAGING ASSOCIATION AND BALANCING OF A MESH DEVICE INA
`
`MESH NETWORK,”filed November 21, 2008 (TR0020-US); and
`
`serial number
`
`entitled "System And Method For Operating Mesh Devices
`
`In Multi-Tree Overlapping Mesh Networks", filed November 21, 2008 (TR0038-US).
`
`-3-
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`FIELD OF THE INVENTION
`
`routing
`for
`systems
`and
`to methods
`generally
`pertains
`invention
`[0003] This
`communications and messages within a mesh network and more particularly to routing
`
`algorithms that optimize mesh networkresourceuse.
`
`BACKGROUNDOF THE INVENTION
`
`[0004] A mesh networkis a wireless network configured to route data between mesh device
`
`nodes within the network.
`
`It allows for continuous connections and reconfigurations around
`
`broken or blocked paths by retransmitting messages from node to node until a destination is
`
`reached. Mesh networks differ from other networks in that nodes can all connect to each
`
`other via multiple hops.
`
`Thus, mesh networks are self-healing:
`
`the network remains
`
`operational when a node or a connectionfails.
`
`[0005] Advanced Metering Infrastructure (AMI) or Advanced Metering Management
`
`(AMM) are systems that measure, collect and analyze utility usage, from advanced devices
`
`such as electricity meters, gas meters, and water meters, through a network on request or a
`
`pre-defined schedule. This infrastructure includes hardware, software, communications,
`
`customer associated systems and mesh device Data managementsoftware. The infrastructure
`
`collects and distributes information to customers, suppliers, utility companies and service
`
`providers. This enables these businessesto either participate in, or provide, demand response
`
`solutions, products and services. Customers may alter energy usage patterns from normal
`
`consumption patterns in response to demand pricing.
`
`This improves system load and
`
`reliability.
`
`[0006] The mesh gate may interface between the mesh network and a server over a wide
`
`area network (WAN). Each mesh device may associate with a mesh network and meshgate,
`
`leaving the mesh network vulnerable to a failure in the mesh gate.
`
`In addition, there may be
`
`limited paths between mesh devices within the mesh network.
`
`SUMMARYOF THE INVENTION
`
`[0007] An access point periodically calculates an optimal path from each associated mesh
`
`device to the access point. The access point also transmits the optimal path to each mesh
`
`device. A mesh network routes messages and other communications between nodes. Nodes
`
`of the mesh network can include a mesh gate and at least one mesh device. Tree routing may
`
`be used to determine an optimal route from a mesh device to the mesh gate via the mesh
`
`network by using neighbor information at each mesh device on the path. Source routing may
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`be used to determine an optimal path from the mesh gate to a mesh device by using neighbor
`
`information of the entire mesh network at the mesh gate. Mesh routing may be used to
`
`determine an optimal route from a first mesh device to a second mesh device. Routes may be
`
`periodically optimized for a variety of performance factors.
`
`[0008]
`
`In one aspect, there is provided a system for optimizing communication paths within
`
`a mesh network,including: meansfor initiating a mesh network, the mesh network including
`
`at least one mesh device; a receiver receiving registration information from each mesh device
`
`of the mesh network; a memory storage for storing mesh device information in an accessible
`
`memory; a processor logic, responsive to predeterminedtrigger, for calculating an optimal
`
`path from each mesh device, wherein the optimal path includes a set of mesh device
`
`addresses corresponding to a set of mesh devices along which a message can be forwarded;
`
`and a transmitter for transmitting the calculated optimal path to each mesh device.
`
`[0009]
`
`In another aspect,
`
`there is provided a computer program stored in a computer
`
`readable form for execution within a processor and memory associated memory to execute a
`
`method for optimizing communication paths within a mesh network, including: initiating a
`
`mesh network, the mesh network including at least one mesh device; receiving registration
`
`information from each mesh device of the mesh network; storing mesh device information in
`
`an accessible memory; responsive to predetermined trigger, calculating an optimal path from
`
`each mesh device, wherein the optimal path includes a set of mesh device addresses
`
`corresponding to a set of mesh devices along which a message can be forwarded; and
`
`transmitting the calculated optimal path to each mesh device.
`
`[0010]
`
`In another aspect, there is provided a method for transmitting a message over a mesh
`
`network via a routing, the method including: associating a first mesh device with a mesh
`network, the mesh network managed by anaccesspoint; identifying a next mesh device from
`
`amonga plurality of neighbor mesh devices; and transmitting the message to the identified
`
`next mesh device.
`
`[0011]
`
`In another aspect, there is provided a method for transmitting a message over a mesh
`
`network via a routing, the method including: associating a first mesh device with a mesh
`
`network, the mesh network managed by an access point; and identifying a next mesh device
`
`from amonga plurality of neighbor mesh devices, the next mesh device being identified by
`
`one of:
`
`(i) using tree routing comprising: receiving neighbor information from a set of
`
`neighboring mesh devices; and identifying the next mesh device by selecting a next mesh
`
`‘device from the set of neighboring mesh devices in response to a request to transmit a
`
`message to the access point, wherein the next mesh device is closer to the access point; (ii)
`
`-5-
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`using source routing comprising: identifying the next mesh device by receiving a next mesh
`
`device address from the access point, wherein the next mesh device is part of an optimal path
`
`to the access point; or (iii) using mesh routing comprising: broadcasting an optimal path
`
`query to neighboring mesh devices in response to a request to transmit a message to a
`
`receiving mesh device; receiving replies from the neighboring mesh devices; and identifying
`
`the next mesh device by selecting a next mesh device by calculating an optimal path, the
`
`optimal path including an address of a next mesh device.
`
`[0012}
`
`In another aspect, there is provided a system for transmitting a message over a mesh
`
`network via a routing, the system including: means associating a first mesh device with a
`
`mesh network, the mesh network managed by an access point; and meansfor identifying a
`
`next mesh device from amonga plurality of neighbor mesh devices, the next mesh device
`
`being identified by one of: (i) using tree routing comprising: receiving neighbor information
`
`from a set of neighboring mesh devices; and identifying the next mesh device by selecting a
`
`next mesh device from the set of neighboring mesh devices in response to a request to
`
`transmit a message to the access point, wherein the next mesh device is closer to the access
`
`point; (ii) using source routing comprising: identifying the next mesh device by receiving a
`
`next mesh device address from the access point, wherein the next mesh device is part of an
`
`optimal path to the access point; or
`
`(iii) using mesh routing comprising: broadcasting an
`
`optimal path query to neighboring mesh devices in response to a request to transmit a
`
`message to a receiving mesh device; receiving replies from the neighboring mesh devices;
`
`and identifying the next mesh device by selecting a next mesh device by calculating an
`
`optimal path, the optimal path including an address of a next mesh device.
`
`[0013}
`
`In another aspect,
`
`there is provided a computer program stored in a computer
`
`readable form for execution within a processor and memory associated memory to execute a
`
`method for transmitting a message over a mesh network via a routing, the method including:
`
`associating a first mesh device with a mesh network, the mesh network managed by an access
`
`point; and identifying a next mesh device from amongaplurality of neighbor mesh devices,
`
`the next mesh device being identified by one of: (i) using tree routing comprising: receiving
`
`neighbor information from a set of neighboring mesh devices; and identifying the next mesh
`
`device by selecting a next mesh device from the set of neighboring mesh devices in response
`
`to a request to transmit a message to the access point, wherein the next mesh device is closer
`
`to the access point; (ii) using source routing comprising: identifying the next mesh device by
`
`receiving a next mesh device address from the access point, wherein the next mesh device is
`
`part of an optimal path to the access point; or
`
`(iii) using mesh routing comprising:
`
`-6-
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`broadcasting an optimal path query to neighboring mesh devices in response to a request to
`
`transmit a message to a receiving mesh device; receiving replies from the neighboring mesh
`
`devices; and identifying the next mesh device by selecting a next mesh device by calculating
`
`an optimal path, the optimal path including an address of a next mesh device.
`
`[0014]
`
`In another aspect, there is provided a method for transmitting a message over a mesh
`
`network via tree routing, the method including: associating a first mesh device with a mesh
`
`network, the mesh network managed byan access point; receiving neighbor information from
`
`a set of neighboring mesh devices; responsive to a request to transmit a message to the access
`
`point, selecting a next mesh device from the set of neighboring mesh devices, wherein the
`
`next mesh deviceis closer to the access point; and transmitting the message to the next mesh
`
`device.
`
`[0015]
`
`In another aspect, there is provided a system for transmitting a message over a mesh
`
`networkvia tree routing, the system including: an association logic unit for associating a first
`
`mesh device with a mesh network, the mesh network managed by an access point; a receiver
`
`for receiving neighbor information from a set of neighboring mesh devices; a selection logic
`
`unit responsive to a request to transmit a message to the access point, selecting a next mesh
`
`device from the set of neighboring mesh devices, wherein the next mesh device is closer to
`
`the access point; and a transmitter for transmitting the message to the next mesh device.
`
`[0016]
`
`In another aspect,
`
`there is provided a computer program stored in a computer
`
`readable form for execution within a processor and memory associated memory to execute a
`
`method for transmitting a message over a mesh network via tree routing,
`
`the method
`
`including: associating a first mesh device with a mesh network, the mesh network managed
`
`by an access point; receiving neighbor information from a set of neighboring mesh devices;
`
`responsive to a request to transmit a message to the accesspoint, selecting a next mesh device
`
`from the set of neighboring mesh devices, wherein the next mesh device is closer to the
`
`access point; and transmitting the message to the next mesh device.
`
`[0017]
`
`In another aspect, there is provided a system for transmitting a message over a mesh
`
`networkvia tree routing, the system including: means for associating a first mesh device with
`
`a mesh network,
`
`the mesh network managed by an access point; means for receiving
`
`neighbor information from a set of neighboring mesh devices; means responsive to a request
`
`for transmitting a message to the access point, selecting a next mesh device from the set of
`
`neighboring mesh devices, wherein the next mesh device is closer to the access point; and
`
`meansfor transmitting the message to the next mesh device.
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`[0018]
`
`In another aspect, there is provided a method for transmitting a message over a mesh
`
`network via source routing, the method including: associating a first mesh device with a mesh
`
`network,
`
`the mesh network managed by an access point; receiving a next mesh device
`
`address from the access point, wherein the next mesh device is part of an optimal path to the
`
`access point; and responsive to a request
`
`to transmit a message to the access point,
`
`transmitting the message to the next mesh device.
`
`[0019]
`
`In another aspect, there is provided a system for transmitting a message over a mesh
`
`network via source routing, the system including: an association logic unit for associating a
`
`first mesh device with a mesh network, the mesh network managed by an accesspoint; a
`
`receiver for receiving a next mesh device address from the access point, wherein the next
`
`mesh deviceis part of an optimal path to the access point; and a transmitter responsive to a
`
`request to transmit a message to the access point, for transmitting the message to the next
`
`meshdevice.
`
`[0020]
`
`In another aspect,
`
`there is provided a computer program stored in a computer
`
`readable form for execution within a processor and memory associated memory to execute a
`
`method for transmitting a message over a mesh network via source routing, the method
`
`including: associating a first mesh device with a mesh network, the mesh network managed
`
`by an access point; receiving a next mesh device address from the access point, wherein the
`
`next mesh deviceis part of an optimal path to the access point; and responsive to a request to
`
`transmit a messageto the access point, transmitting the message to the next mesh device.
`
`[0021]
`
`In another aspect, there is provided a system for transmitting a message over a mesh
`
`network via source routing, the system including: means for associating a first mesh device
`
`with a mesh network, the mesh network managed by an access point; means for receiving a
`
`next mesh device address from the access point, wherein the next mesh device is part of an
`
`optimal path to the access point; and means responsive to a request to transmit a messageto
`
`the access point, for transmitting the message to the next mesh device.
`
`In another aspect, there is provided a method for transmitting a message over a mesh
`[0022]
`network via meshrouting, the method including: associating a first mesh device with a mesh
`
`network, the mesh network managed by an access point; responsive to a request to transmit a
`
`messageto a receiving mesh device, broadcasting an optimal path query to neighboring mesh
`
`devices;
`
`receiving replies from the neighboring mesh devices; calculating an optimal path,
`
`the optimal path including an address of a next mesh device; and transmitting the message to
`
`the next mesh device.
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`[0023]
`
`In another aspect, there is provided a system for transmitting a message over a mesh
`
`network via mesh routing, the system including: an association logic unit for associating a
`
`first mesh device with a mesh network, the mesh network managed by an access point; a
`
`transmitter responsive to a request to transmit a message to a receiving mesh device, for
`
`broadcasting an optimal path query to neighboring mesh devices; a receiver for receiving
`
`replies from the neighboring mesh devices; a processing logic for calculating an optimal path,
`
`the optimal path including an address of a next mesh device; the transmitter being adapted for
`
`transmitting the message to the next mesh device.
`
`{0024}
`
`In another aspect,
`
`there is provided a computer program stored in a computer
`
`readable form for execution within a processor and memory associated memory to execute a
`
`method for transmitting a message over a mesh network via mesh routing,
`
`the method
`
`including: associating a first mesh device with a mesh network, the mesh network managed
`
`by an access point; responsive to a request to transmit a message to a receiving mesh device,
`
`broadcasting an optimal path query to neighboring mesh devices; receiving replies from the
`
`neighboring mesh devices; calculating an optimal path, the optimal path including an address
`
`of a next mesh device; and transmitting the message to the next mesh device.
`
`[0025]
`
`In another aspect, there is provided a method for route discovery within a mesh
`
`network via mesh routing, the method including: associating a first mesh device with a mesh
`
`network, the mesh network managed by an access point; responsive to receiving an optimal
`
`path query from a sending mesh device,
`
`re-broadcasting the optimal path query to
`
`neighboring mesh devices; responsive to receiving an optimal path reply, calculating an
`
`optimal path; and replying to the sending mesh device with the optimal path.
`
`[0026]
`
`In another aspect, there is provided a system for route discovery within a mesh
`
`network via mesh routing, the system comprising: means associated with a mesh network,the
`
`mesh network managed by an access point; means responsive to receiving an optimal path
`
`query from a sending mesh device, for re-broadcasting the optimal path query to neighboring
`
`mesh devices; means responsive to receiving an optimal path reply, for calculating an optimal
`
`path; and meansfor replying to the sending mesh device with the optimal path.
`
`[0027]
`
`In another aspect,
`
`there is provided a computer program stored in a computer
`
`readable form for execution within a processor and memory associated memory to execute a
`
`method for route discovery within a mesh network via mesh routing, the method including:
`
`associating a first mesh device with a mesh network, the mesh network managed by an access
`
`point; responsive to receiving an optimal path query from a sending mesh device,
`
`re-
`
`broadcasting the optimal path query to neighboring mesh devices; responsive to receiving an
`
`-9-
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`optimalpath reply, calculating an optimal path; and replying to the sending mesh device with
`
`‘the optimal path.
`
`[0028] Other aspects and features will be apparent from the included description, drawings,
`
`and accompanyingclaims.
`
`[0029] This Summary is providedto introduce a selection of concepts in a simplified form
`
`that are further described below in the Detailed Description. This Summary is not intended to
`
`identify key features or essential features of the claimed subject matter, nor is it intended to
`
`be used to limit the scope of the claimed subject matter.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`{0030] FIG. 1A illustrates an example system for providing communications in an AMI
`
`system utilizing a tree routing scheme.
`
`[0031]
`
`FIG. 1B illustrates an example system for providing communications in an AMI
`
`system utilizing a source routing scheme.
`[0032]
`FIG. 1C illustrates an example system for providing communications in an AMI
`system utilizing a mesh routing scheme.
`
`[0033]
`
`FIG. 1D illustrates an example system for optimizing routes within a mesh network.
`
`[0034] FIG. 2A illustrates an example mesh device for use within a mesh network.
`
`FIG. 2B illustrates an example meshgate for use within a mesh network.
`[0035]
`[0036] FIG.3 illustrates an example networkstack for use within a meshradio.
`[0037]
`FIG. 4A illustrates an example procedure for tree routing and route optimization in a
`
`mesh network.
`
`[0038] FIG. 4B illustrates an example procedure for source routing in a mesh network.
`
`[0039]
`
`FIG. 4C illustrates an example procedure for mesh routing scheme in a mesh
`
`network.
`
`-10-
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`[0040]
`
`FIG. 1A illustrates an example system for providing communications in an AMI
`
`system utilizing a tree routing scheme. A mesh device wishing to send a message to the mesh
`
`gate may look up a neighbor information table and select a neighbor closer to the mesh gate.
`
`A mesh gate mayalso be referred to as a NAN-WAN(Neighborhood Area Network- Wide
`
`Area Network) gate or an access point. Other fields stored in the neighbor information table
`
`may include a path signal quality. The message may be transmitted to the neighbor for
`
`forwarding to the mesh gate. The neighbor information table may be updated via periodic
`
`neighbor information exchanges with neighboring meshdevices.
`
`[0041] When the forwarding mesh device receives the message,it also looks up a neighbor
`
`information table and selects a mesh device closer to the mesh gate.
`
`In this way, the message
`
`is transmitted from one mesh device to another, until it reaches the mesh gate. A temporary
`
`path may be created at each forwarding mesh device. The temporary path may allow a
`
`response to be transmitted back to the sending mesh device, if required.
`
`“Femporary paths
`
`may bestored in a memory of forwarding mesh devices for a predetermined interval.
`
`
`
`[0042] Inthe example of FIG. 1A, the mesh network A 100 mayincludeaplurality of mesh
`
`gates and meshdevices, such as meters, which together cover a geographical area.
`
`In a non-
`
`limiting embodiment for an urban or metropolitan geographical area, there may be between1
`
`and 100 mesh gates, but this is not a limitation of the invention.
`
`In one embodiment, each
`
`mesh gate supports approximately 400 meters, depending on system requirements, wireless
`
`reception conditions, available bandwidth, and other considerations.
`
`It will be appreciated
`
`that it is preferable to limit meter usage of bandwidth to allow for future upgrades. The
`
`meters mayincludeutilities sensors and be part of an AMI system and communicate with the
`
`mesh gates over the mesh network. For example,
`
`the AMI system may monitor utilities
`
`usage, such as gas, water, or electricity. Alternative mesh devices include thermostats, user
`displays, and other components for monitoring and controllingutilities.
`
`[0043]
`
`Inthe example of FIG. 1A, the mesh gate A 102 may provide a gateway between the
`
`mesh network and a server. The mesh gate A 102 mayinclude a meshradio to communicate
`
`with mesh devices on the mesh network and a WAN communication interface to
`
`communicate with a server over the WAN.
`
`In the example of FIG. 1A, the mesh gate A 102 may aggregate information from
`[0044]
`meters within the mesh network and transmit the information to the server. The mesh gate A
`
`mayalso forward individual communications from a mesh device to the server. While only
`
`-ll-
`
`

`

`WO 2009/067251
`
`PCT/US2008/013019
`
`one mesh gate is depicted in the mesh network A, any number of mesh gates may be
`
`deployed,
`
`for example,
`
`to improve transmission bandwidth to the server and provide
`
`redundancyin the mesh network.
`
`[0045] The mesh gate mayalso be knownas a collector, a concentrator, or an access point.
`
`[0046]
`
`In the example of FIG. 1A, the meters A 104, B 106, C 108, D 110, E 112, and F
`
`114 may each be a mesh device associated with the mesh network A through direct or
`
`indirect communications with the mesh gate A. Each meter may forward transmissions from
`
`other meters within the mesh network towards the mesh gate. While only six meters are
`
`depicted, any number of meters may be deployed to cover any numberofutility lines or
`
`locations within the mesh network.
`
`[0047]
`
`In the example of FIG. 1A, as depicted, only meters A 104 and D 110 are in direct
`
`communications with mesh gate A 102. However, meters B 106, E 112 and F 114