Title of Invention

METHOD AND APPARATUS FOR RELAYING INFORMATION IN AN AD-HOC NETWORK

Abstract To address the need for routing communications within an ad-hoc network that reduces the amount of battery consumption, a method and apparatus (400) for routing such communications is provided. Mitigation of battery consumption occurs by prioritizing (505) those units utilized for relay purposes. Those units using real-time services are prioritized over active units using non-real time services. By using actively transmitting units as relays as a first choice, battery consumption of the network as a whole can be greatly reduced.
Full Text Method and apparatus for Relaying information in an Ad-Hoc Network
Field of the Invention
The present invention relates generally to communication systems and in
particular, to a method and apparatus for relaying information in ad-hoc networks.
Background of the Invention
A communication system may use ad-hoc networking to improve its
performance. As described in the international application published under the Patent
Cooperation Treaty, publication number WO 00/54539, ROUTING IN A Multi-
Station NETWORK, which is incorporated by reference herein, increased coverage
reliability and increased throughput are some of the benefits of using ad-hoc
networking. In cellular communication systems utilizing ad-hoc networking, cellular
handsets are equipped to operate in both the cellular and ad-hoc networks. Users
access the cellular infrastructure through the ad-hoc network whenever they cannot
access the cellular network directly, or when they find it more advantageous to do so.
Using an ad-hoc air interface, such users transmit to another user, which forwards
(relays) the transmission to the infrastructure through the cellular air interface. Such a
system is shown in FIG. 1.
As shown, remote (or mobile) unit 102 existing within area 101 is unable to
communicate directly with infrastructure equipment 106. By utilizing ad-hoc
networking, remote unit 102 communicates with remote unit 104 (via ad-hoc air
interface 103). Remote unit 104 then relays the communication to infrastructure 106
via air interface 105.
Because a mobile unit that is acting as a relay to other mobiles is consuming
its battery reserve, there is a general concern that users would be unwilling to act as a
relay if battery consumption is too great. This would hinder the development of ad-
hoc networking in cellular systems. Therefore, a need exists for a method and
apparatus for relaying communications within an ad-hoc network that reduces the
amount of battery consumption for those remote units relaying communications.
Brief Description of the Accompanying Drawings
FIG. 1 is a block diagram of an ad-hoc communication system.
FIG. 2 is a graph comparing prior art ad-hoc networking with an ad-hoc
network operated in accordance with the preferred embodiment of the present
invention.
FIG. 3 is a graph illustrating current drain for a communication system
utilizing ad-hoc networking to reduce average battery consumption.
FIG. 4 is a block diagram of a mobile unit in accordance with the preferred
embodiment of the present invention.
FIG. 5 is a flow chart showing operation of the mobile unit of FIG. 2 in
accordance with the preferred embodiment of the present invention.
Detailed Description of the Drawings
To address the need for routing communications within an ad-hoc network
that reduces the amount of battery consumption, a method and apparatus for routing
such communications is provided herein. In accordance with the preferred
embodiment of the present invention mitigation of battery consumption will occur by
prioritizing those units utilized for relay purposes. The prioritization scheme favors
actively transmitting units over inactive units. In yet another embodiment, those units
using real-time services are prioritized over active units using non-real time services.
As will be shown below, by using actively ttansmitting units as relays as a first
choice, battery consumption of the network as a whole can be greatly reduced. Thus,
by avoiding relaying through inactive units, one can reduce the average current
consumption in cellular handsets operating in the system.
The present invention encompasses a method for relaying information in an
ad-hoc network. The method comprises the steps of identifying a plurality of devices
that can serve as relay devices and identifying attributes for the plurality of devices.
Based on the attributes, a device that will result in a best system performance is
determined as the relay device and is utilized for relaying the information.
The present invention additionally encompasses a method comprising the
steps of identifying a plurality of devices that can serve as an ad-hoc relay, identifying
which of the plurality of devices is actively transmitting, and utilizing a device that is
actively transmitting for the ad-hoc relay.
The present invention additionally encompasses an apparatus comprising logic
circuitry utilized for identifying a plurality of devices that can serve as an ad-hoc
relay, identifying which of the plurality of devices is actively transmitting, and
choosing an actively-transmitting device to act as the ad-hoc relay. The apparatus
additionally comprises a transmitter for sending information to the actively-
transmitting device utilizing a first over-the-air protocol, causing the actively-
transmitting device to transmit the information to infrastructure equipment utilizing a
second over-the-air protocol.
The present invention additionally encompasses an apparatus comprising logic
circuitry utilized for identifying a plurality of devices that can serve as an ad-hoc
relay, identifying a plurality of attributes for the identified devices, and choosing a
device to act as the ad-hoc relay based on the identified attributes, wherein the device
chosen maximizes system performance. The apparatus additionally comprises a
transmitter for sending information to the device utilizing a first over-the-air protocol,
causing the device to transmit the information to infrastructure equipment utilizing a
second over-the-air protocol.
Prior to describing ad-hoc routing in accordance with the preferred
embodiment of the present invention, the following text and equations are provided to
set the necessary background for utilization of the preferred embodiment of the
present invention.
Considering the average active current consumption of the cellular device, this
current can be represented by the equation below.
Where:
E[I] is the expected average current consumption of a given cellular
device while active. This average directly relates to the talk-
time of a cellular device;
Pact_relayed is the probability that this device is being relayed by another
device;
Iact_relayed is the current consumed while being relayed;
Pact_relaymg is the probability that an active device is relaying messages from
another device;
Iact_relaying is the current consumed by an active cellular device that is
communicating directly with the base station and is relaying
messages from another cellular device;
Idirect is the current consumed when the cellular device communicates
directly with the base station and is not relaying messages from
any cellular device;
Pinactive is the ratio of time that the given device is in inactive state (i.e., not
carrying any communication from its owner);
Pactive is the ratio of time that the given device is in active state;
Pinct_relaying is the probability that the given cellular device is relaying
messages from another device while it is in inactive state;
Iinact_relaying is the current consumed by the inactive cellular device while
relaying messages from another cellular device; and
P inactive/pactive . P inact_relaying.I inact_relayingrepresents the impact of inactive relaying

in the average active current consumption.
Using the representation above, in the preferred embodiment of the present
invention Pact_relaying is increased while decreasing Pinact_relaying. Intuitively, note that
the additional current consumption required by a relay which is already active, is far
less than the additional current required by the unit which is inactive and needs to
power its transmitter to perform the relay function. Thus, by avoiding relaying
through inactive units, one can reduce the average current consumption in cellular
handsets operating in the system. Another way to intuitively see the benefit of
utilizing active transmitters as relay stations is to consider 20 active users in a cell. If
5 inactive users are relaying communication from 5 active users, there actually exists
25 cellular devices consuming battery resources. However, if these 5 active users
were being relayed by 5 other active users, the number of cellular devices consuming
battery resources would simply be 20.
In order to provide quantitative measures by avoiding relaying through
inactive units, equation (1) can be evaluated for both relaying through active as well
as inactive users. In order to simplify the model, a uniform random distribution of
active and inactive users in the cell area is considered.

Given N users being relayed, per the prior art, active units are given as much
consideration when relaying as any inactive unit so Pact_relaymg and P inact_relaying is given
by:
where
Pimange is the chance that one of the JV users can reach the given relay candidate.
Given the maximum distance (Rmax_BT) between relay and relayed units, this
probability can be approximated by the ratio (Rmax_BT I RmaxjG)2, where Rmaxja is the
cell radius. Pseiecied is the chance that the given relay candidate will be chosen among
all other relay candidates. Without relaying specifically through active users, this
probability is approximated by the inverse of the number of relay candidates, which is
equal to the number of inactive and available active units inside the circle area with
radius RmaxBT-
However, by relaying only through active users, Pact_reiqytng is increased and
Pinact_relaying is decreased. Pact-relaying is still given by the equation above, but Pseiecied is
the inverse of the number of only active relay candidates inside the area with radius
Rmax_BT- P inact_nalytng is given by:
where
Pm act represents the chance that no active relay candidates are available to serve a
given user seeking to be relayed, which can be approximated by:

where Nact is the number of active relay candidates in the system. Note that the above
formulation means that inactive relay candidates will only be selected if no active
relay units are inside the area with radius Rima_BT-
Using the above formulation, FIG. 2 compares prior art ad-hoc networking
with an ad-hoc network operated in accordance with the preferred embodiment of the
present invention. In particular, FIG. 2 shows the percentage reduction in the average
current consumption for different values of Preiayed and several ratios of Rmax bt /
P-maxjG- The results consider a uniform user density of 21242 users/sq km, with an
average of 3% active users.
The results show that the average current consumption reduces as the number
of users being relayed increases, as expected. In a scenario with voice users, 100-
meter cells, 667 users per cell (20 active), in-building propagation models and 50%
users seeking relay, computer simulations show a 26% reduction in the average
current consumption, in line with the analytical approximation.
The results above consider 3% of active users. The benefit is increased when
the percentage of active users is increased. Similarly, the benefit increases as the user
density increases for a given ratio of active users.
Average current drain is not only reduced when compared against prior art,
but using active users as relays also allows reduction of average current consumption
when compared to cellular systems without ad hoc networking. FIG. 3 illustrates this
benefit for different Rmax_BT / Rmax_3G ratios. Note that, without strictly using active
users as relays, the implementation of ad hoc networking would cause an increase in
the average current consumption. Using technologies that allow Rmax_BT / Rmax_3G
ratios of 0.3 or more, using active users as relays actually provides a decrease in the
average current consumption when compared to the cellular system without ad hoc
networking. Simulation results also confirm the analytical predictions shown below,
showing 13% reduction in the average current consumption (for Rmax_BT / Rmax_3G =
0.4, and 50% users seeking relay).
FIG. 4 is a block diagram of mobile unit 400 in accordance with the preferred
embodiment of the present invention. As shown, mobile unit 400 comprises
transmitter 401, receiver 407, buffer 405, and logic circuitry 403. As discussed
above, transmitter 401 and receiver 407 are designed to operate over both a cellular
air interface (e.g., GSM, CDMA, WCDMA, . . ., etc.) and an ad-hoc networking air
interface (e.g., BLUETOOTH, 802.11, . . . , etc.). As one of ordinary skill in the art
will recognize, typically the cellular air interface (utilizing a cellular over-the-air
protocol) serves long-range communication, while the ad-hoc air interface (utilizing
an ad-hoc over-the-air protocol) serves short-range communication.
While remote unit 400 is acting as a relay, it is continuously receiving
transmissions 409 from another remote unit utilizing the ad-hoc air interface and
relays (prior to, or after, buffering via buffer 405) these transmissions to infrastructure
equipment via uplink communication signal 411 utilizing the cellular air interface.
Similarly, when remote unit 400 is relaying communication through another remote,
or mobile unit, remote unit 400 is generally receiving downlink communications over
the cellular air interface and transmitting uplink communications to another remote
unit via the ad-hoc air interface.
During operation, logic unit 403 serves as an ad-hoc networking module that
is constantly in a "standby" or low-power consumption mode. Logic unit 403
periodically enters into an "inquiry mode" (e.g., BLUETOOTH inquiry scan mode).
During the inquiry mode, mobile units constantly share information with each other
regarding their ability to act as a relay, or their need to be relayed. In particular, for
ad-hoc networking utilizing the BLUETOOTH standard, the mobile unit will hop
through frequencies sending inquiries to standby devices listening for such inquiries.
When the standby device hears the inquiry, it responds with its address and timing
information to enable future communications. In the preferred embodiment of the
present invention the standby device will also provide information on whether or not
the standby device is actively transmitting over the cellular network as well as other
attributes (such as, but not limited to whether the remote unit is A/C powered,
whether the remote unit has low battery reserves, . . . , etc.). When finished, the
inquiring mobile will have identified a list of neighbor devices that the mobile can
serve as relay devices through the ad hoc interface, along with the attributes of these
mobiles. These devices then become relay candidates.
If a mobile then wishes to be relayed, logic unit 403 will choose a relay among
all candidates surveyed. In the preferred embodiment of the present invention logic
unit rank-orders these units in order to choose relay candidates that will result in the
best system performance, which in this case comprises a relay device that has a
minimum effect on overall system battery consumption. In particular, those units
with low battery reserves will be placed at the bottom of the list, while those units that
are A/C powered will be placed at the top of the list. Furthermore, those units that are
actively transmitting will be placed higher on the list than those units that are inactive.
Thus, in accordance with the preferred embodiment of the present invention, relay
candidates are chosen as follows:
1. Choose unit that is A/C powered.
2. Choose unit that is actively transmitting with an established cellular
connection.
3. Choose inactive unit with large battery reserves.
4. Choose unit with low battery reserves.
In a further embodiment of the present invention, the actively transmitting
mobile units are further categorized with those units using real-time services preferred
over those units not using real-time services. Real-time services are distinguished by
transmissions that do not tolerate much delay (e.g., typical voice transmission). Non-
real-time services are distinguished by transmissions that may tolerate longer delays
(e.g., web browsing). In the preferred embodiment of the present invention those units
using real-time services are distinguished by having its transmitter 401 either
constantly activated or activated many times per second, with short time intervals
between consecutive transmitter activations (e.g., typical voice transmission has a
40% duty cycle), while those using non-real-time services are characterized by having
its transmitter 401 inactive in the majority of the communication time (e.g., web
browsing), in which most of the communications is directed from the infrastructure to
the mobile unit. Because a remote unit looking to relay information will prioritize
those units to choose as relay units, overall system battery consumption is greatly
reduced.
In a further embodiment of the present invention, since the transmitter of the
active unit 104 selected to be the relay may have periods of inactivity during real-time
or non-real-time data transmission, non-real-time data from unit 102 may be buffered
inside unit 104 in order to be transmitted coincident with data originated inside unit
104, thus avoiding an increase in the transmitter activations of unit 104, which avoids
the increase in the average current consumption. Thus, a relaying remote unit will
intermittently transmitting internally generated information to a first network while
receiving relay information (externally generated) from a remote unit over a second
network. The relay information is buffered until it is determined when the internally
generated information is to be transmitted to the first network, at which time the
buffered information is transmitted along with internally generated information the
remote unit transmits to the first network.
In a further embodiment of the present invention, A/C powered units are
categorized as permanent or temporary A/C powered units. An example of a
temporary A/C powered unit is a mobile unit resting in a battery charger cradle. While
it is on the cradle, it is an A/C powered unit. When it is removed from the battery
charger cradle, it is battery powered. Thus, the present invention further proposes the
prioritization of permanent A/C powered units over temporary A/C powered units
since temporary A/C powered units may become battery powered units during a relay
operation, causing additional battery consumption.
In a further embodiment of the present invention, the number of connections
being relayed by an actively transmitting mobile unit is also used as an attribute to
decide the relay unit.
FIG. 5 is a flow chart showing operation of the remote unit of FIG. 4 in
accordance with the preferred embodiment of the present invention. The logic flow
begins at step 501 where remote unit 400 determines the need to relay information
through a second remote unit. The need to relay information may be due inter alia,
because of an inability to communicate with the cellular system, to allow any user to
benefit from the low-current consumption when being relayed, to take advantage of
relays with a better channel quality,..., etc.
At step 503, the remote unit enters an "inquiry mode", surveying all local
remote units for potential relay devices. As discussed above, in the preferred
embodiment of the present invention the remote unit will determine attributes, or
performance characteristics for all relay candidates. In particular, information such as
whether the relay candidate is A/C powered, whether the relay candidate has an
established and active connection to the infrastructure equipment, . . . , etc. will be
provided to the remote unit. At step 505, the remote unit will rank-order potential
candidates and choose the remote unit that will result in the best system performance.
In particular, those remote units are chosen that will have a minimal effect on battery
consumption for relay purposes. As discussed above, those units that are A/C
powered are preferably chosen, followed by those units with an active connection to
the infrastructure. At step 507, information is relayed through the chosen remote unit.
As discussed above, by prioritizing relay stations as such, current drain is not
only reduced, but using active users as relays also allows reduction of average current
consumption in the system as a whole when compared to cellular systems without ad
hoc networking.
While the invention has been particularly shown and described with reference
to a particular embodiment, it will be understood by those skilled in the art that
various changes in form and details may be made therein without departing from the
spirit and scope of the invention. For example, it is expected that the benefits
presented here are also applicable to the case with more than 1 relay. Additionally,
although the above description was give with respect to relaying within a cellular
communication systems, one of ordinary skill in the art will recognize that relaying as
described above may occur in other types of communication systems. It is intended
that such changes come within the scope of the following claims.
WE CLAIM :
1. A method for relaying information in an ad-hoc network, the method
comprising:
identifying a plurality of devices that can serve as relay devices;
identifying attributes for the plurality of devices, the attributes selected
from the group consisting of: whether each device is A/C powered, whether each
device has a large battery reserve, whether each device is actively
communicating, and whether each device is using a real-time service;
based on the attributes, choosing a device from the plurality of devices; and
utilizing the chosen device for relaying the information.
2. The method as claimed in claim 1 wherein utilizing the chosen device for
relaying the information comprises sending information to the chosen device
utilizing a first over-the-air protocol, causing the chosen device to transmit the
information to infrastructure equipment utilizing a second over-the-air protocol.
3. An apparatus comprising:
logic circuitry utilized for identifying a plurality of devices that can serve as
ad-hoc relay devices, for identifying attributes for the plurality of identified
devices, the attributes selected from the group consisting of: whether each
device is A/C powered, whether each device has a large battery reserve,
whether each device is actively communicating, and whether each device is
using a real-time service, and for choosing a device from the plurality of device,
the choosing based on the identified attributes; and
a transmitter for sending information to the chosen device utilizing a first
over-the-air protocol, causing the chosen device to transmit the information to
infrastructure equipment utilizing a second over-the-air protocol.

To address the need for routing communications within an ad-hoc network
that reduces the amount of battery consumption, a method and apparatus (400)
for routing such communications is provided. Mitigation of battery consumption
occurs by prioritizing (505) those units utilized for relay purposes. Those units
using real-time services are prioritized over active units using non-real time
services. By using actively transmitting units as relays as a first choice, battery
consumption of the network as a whole can be greatly reduced.

Documents:

308-kolnp-2005-abstract.pdf

308-kolnp-2005-assignment.pdf

308-kolnp-2005-claims.pdf

308-KOLNP-2005-CORRESPONDENCE-1.1.pdf

308-KOLNP-2005-CORRESPONDENCE.pdf

308-kolnp-2005-description (complete).pdf

308-kolnp-2005-drawings.pdf

308-kolnp-2005-examination report.pdf

308-KOLNP-2005-FOR ALTERATION OF ENTRY IN THE PATENT REGISTER-1.1.pdf

308-KOLNP-2005-FOR ALTERATION OF ENTRY.pdf

308-kolnp-2005-form 1.pdf

308-kolnp-2005-form 18.pdf

308-kolnp-2005-form 3.pdf

308-kolnp-2005-form 5.pdf

308-KOLNP-2005-FORM-27.pdf

308-kolnp-2005-gpa.pdf

308-kolnp-2005-granted-abstract.pdf

308-kolnp-2005-granted-assignment.pdf

308-kolnp-2005-granted-claims.pdf

308-kolnp-2005-granted-correspondence.pdf

308-kolnp-2005-granted-description (complete).pdf

308-kolnp-2005-granted-drawings.pdf

308-kolnp-2005-granted-examination report.pdf

308-kolnp-2005-granted-form 1.pdf

308-kolnp-2005-granted-form 18.pdf

308-kolnp-2005-granted-form 3.pdf

308-kolnp-2005-granted-form 5.pdf

308-kolnp-2005-granted-gpa.pdf

308-kolnp-2005-granted-reply to examination report.pdf

308-kolnp-2005-granted-specification.pdf

308-kolnp-2005-international publication.pdf

308-kolnp-2005-international search report.pdf

308-KOLNP-2005-OTHERS-1.1.pdf

308-kolnp-2005-others.pdf

308-KOLNP-2005-PA.pdf

308-kolnp-2005-pct request form.pdf

308-kolnp-2005-petition under rule 137.pdf

308-kolnp-2005-reply to examination report.pdf

308-kolnp-2005-specification.pdf

308-kolnp-2005-translated copy of priority document.pdf


Patent Number 238706
Indian Patent Application Number 308/KOLNP/2005
PG Journal Number 08/2010
Publication Date 19-Feb-2010
Grant Date 17-Feb-2010
Date of Filing 01-Mar-2005
Name of Patentee MOTOROLA, INC.
Applicant Address 1303 EAST ALGONQUIN ROAD, SCHAUMBURG, IL
Inventors:
# Inventor's Name Inventor's Address
1 BONTA, JEFFREY D 1300 E. MAYFAIR, ARLINGTON HEIGHTS, IL 60004
2 FONSECA, BENEDITO 1300 CAMBIA DRIVE, #5320, SCHAUMBURG IL 60193
3 CALCEV, GEORGE 905 CONCORD LANE, HOFFMAN ESTATES IL 60195
PCT International Classification Number H04Q 7/32
PCT International Application Number PCT/US2003/023628
PCT International Filing date 2003-07-29
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 10/219,900 2003-08-15 U.S.A.