In multihop ad hoc networks that use conventional IEEE 802.11, longtransient resynchronisation states are often generated when multiple
IBSSs merge. A simple modification of the conventional timing
synchronisation method is proposed to reduce such synchronisation bottlenecks. When the proposed modification is applied, aself-adaptive synchronisation ability is observed in simulations,which makes resynchronisation times much shorter and reduces
energy consumption.

Introduction: The ad hoc mode of the IEEE 802.11 standard (hereinafter abbreviated as 802.11) supports the formation of independent basic
service sets (IBSSs) in the absence of an access point. Based on the802.11 media access control (MAC) protocol [1], large mobile ad hocnetworks (MANET) are now being developed. In addition, as the nodes(mobile PCs or PDAs) become smaller, more efficient, power-saving
control is required, and the transmission ranges of nodes should belimited if possible. In such networks, the timing synchronisation function (TSF) is one of the essential integral components, since timing
synchronisation is required for frequency-hopping spread spectrum andsynchronous power-saving control. In this 802.11 TSF, each nodetransmits a beacon that carries timing information only when the nodeis elected through the contention of neighbouring nodes.
This contention is based on a random process and is supposed toprovide a fair election of the beacon transmission node. Most conventional studies on this timing synchronization problem have assumed
closed, isolated networks within a single IBSS [2, 3]. In contrast to such
ideal static cases, timing synchronisation in dynamic environments iscurrently being considered (e.g. for the cases of merging two IBSSs [4]and of resynchronisation in large, multihop networks [5]). In this Letter,
we consider MANET in such dynamic situations, and propose a simple
modification of the 802.11 TSF. Interestingly, this simple modification
greatly reduces the transient resynchronisation time, especially forlarger networks with hundreds of nodes that maintain a relatively
small total number of awake nodes. The reason for the efficiency ofthe present method is also investigated by systematic simulation andanalysis, revealing a kind of self-organised adaptive process thatenables fast resynchronisation.

Synchronisation bottlenecks: We consider the simple, but genericexamples shown in Fig. 1. Systematic simulations of the synchronisation process were carried out by changing the number of nodes as wellas the transmission range (R) of nodes.

IEEE 802.11

proposed (threshold = 2)

proposed (threshold = 1)

proposed (threshold = 0)80
syncbottleneck

60
40
20020

80

1614
12
10
8
64
20

number of awake nodes

H. Tanaka, O. Masugata, D. Ohta, A. Hasegawa and P. DavisAs shown in Fig. 1a, 143 synchronised nodes (denoted by )
belonging to the same IBSS are randomly placed in a 220  220 mgrid, and a node (denoted by s) belonging to another IBSS with a later
TSF timing is then moved to a certain position. Even though this node
is fixed, its transmission range can temporally become wider. This has
the same effect as the above case of node movement. Both the above
situations initiate a resynchronisation process until all the nodes (144nodes in this example) eventually become resynchronised to the later
timing (s). Since this resynchronisation time depends on the transmission range of the nodes as well as on the position of the introduced
node, we systematically change the transmission range (R) from 24 to
360 m (by 4 m intervals) and 10 000 trials are carried out for each R
with a randomly positioned joining node. To consider the worst-casescenario of the synchronisation process, the power-saving timing of theintroduced node is initially set 180 out of phase to that of the original
nodes in these simulations. Namely, the introduced node is awake whenmost of (but not all of) the other nodes are in the power-saving state.
Note that only awake nodes can receive beacons, and a node remains in
its awake state for one beacon period (100 ms: awake=power-savingcycle) directly after the node has transmitted a beacon by beaconcontention (BC). This is the reason why the resynchronisation process
becomes complicated and often requires a long time.
As a limiting case of Fig. 1a, we also consider the case of merging
two IBSSs (cells), as shown schematically in Fig. 1c. This situationarises when two small rooms (in which any two nodes can directlycommunicate) are joined by a short corridor.
To clarify the essential mechanism of the beacon propagation, thepresent simulations assume that node movement can be neglected in theresynchronisation process. In addition, the following simplifying
assumptions are made: (1) the transmission range is time-constantand uniform over the nodes; (2) the transmission delay of the beacons
carrying the TSF timing is negligible compared to a single beacon slot
(50 ms in this case); and (3) small mismatches in clock frequencies arenegligible compared to the timescale of the awake=power-saving cycle(beacon period), as a first approximation. Later, we consider factors (2)and (3) to be non-negligible and analyse their effects.

resynchronisation time, sFast, self-adaptive timing-synchronisation
algorithm for 802.11 MANET

140200260
transmission range R, m

320

resynchronisation time, snumber of awake nodes

10220 m1020

8642020140200260
transmission range R, m

40 50time, s60

70805075
100
number of nodes, N

125

150

7560

320csync
bottleneck

4530
1508030

b12R0a14

beacon collisions

sync
completed025dFig. 2 Simulation data
220 macFig. 1 Beacon propagation in multihop networks
a Initial stateb Beacon collisions during synchronisation bottleneckc Initial state for merging two-cell cased Beacon collisions during bottleneck

bda Average resynchronisation time with respect to transmission range, for case ofFig. 1ab Number of awake nodes during resynchronisation process
c Number of awake nodes in static stated Average resynchronisation time against total number of nodes (N) in an IBSS,
for case of Fig. 1c

The simulation results obtained are summarised in Fig. 2, in which
the averaged resynchronisation times are plotted against the transmission ranges (data plotted with  in Fig. 2a). This data set is obtainedusing a regular array of 144 nodes. For other node configurations,
including the totally random case and the randomly disturbed arraycase, we have observed a pattern similar to that shown in Fig. 2a. For
the case in which the range of R is larger than 140 m, as shown in Fig.
2a, a synchronisation bottleneck emerges. This long resynchronisation

ELECTRONICS LETTERS 3rd August 2006 Vol. 42 No. 16
Techset Composition Ltd, Salisbury

Doc: {IEE}El/Articles/Pagination/51209.3d
Mobile communication

time can be explained by a spatio-temporal pattern of beacon propagations and frequent beacon collisions, as shown in Fig. 1b (for details,see [5]). In other words, this bottleneck comes from the combination of
the multihop network structure and the beacon contention (BC)mechanism in the 802.11 TSF. We analysed this BC process in detailwhen the bottleneck emerged and found that the fairness in beacon
transmission is lost because nodes near the boundary of the network cantransmit beacons more frequently than other nodes. This is because the802.11 TSF adopts a local BC, which is no longer fair when the local
node density is not uniform over the network.
Simple method to reduce synchronisation bottleneck: Since loss offair beacon transmission causes synchronisation bottleneck, an intuitive method of bottleneck reduction is to regulate the beacon transmissions of nodes near the boundary. In the present simulations,nodes with larger BT values near the boundary are selected, whereas
other nodes are selected with smaller BT values. This is because BC
becomes less competitive near the boundary. Therefore, we should
examine what happens when each node regulates the beacon transmission for the case in which the BT is larger than a certain threshold.
To examine this idea concretely and ensure that it is logicallyconsistent with the 802.11 TSF, the following assumptions areintroduced: (i) for a node selected by BC, the beacon transmission
is cancelled if its BT exceeds a given threshold; and (ii) such a nodemaintains its awake state over one beacon period directly after thecancellation of the beacon transmission.
In Fig. 2, we compare three numerical data sets (plotted by þ, *, andu symbols) obtained using the proposed method to that obtained using
the original 802.11 TSF (). These three data sets are obtained byaveraging over 10 000 trials when the BT threshold is set to one, twoand three beacon slots, respectively. It is noted that, even in the worst
instances of these three data, the synchronisation time is shorter thanthat of the 802.11 case. In Fig. 2a (and Fig. 2d), the data plotted bythe þ symbols show a performance that is several times better than the802.11 TSF (plotted by the  symbols), except for certain shorttransmission ranges (R < 60 m). In these simulations, the number ofawake nodes is also analysed systematically both for the resynchronisation process (Fig. 2b) and for the static states after the resynchronisation
has been completed (Fig. 2c), where R is set to 240 m. In Fig. 2b, allthree data sets (þ, *, and u) have a larger number of awake nodes(averaging approximately five awake nodes) than that for the 802.11(). However, the total number of awake nodes required until theresynchronisation is complete becomes smaller in these three cases,
because the resynchronisation time is much shorter than in the 802.11
case. In Fig. 2c, the number of awake nodes is approximately the same(  one node on average) for R larger than 180 m. In addition, in the
proposed method, the total number of beacon transmissions is always
less than that of the 802.11 TSF, which is a direct consequence ofassumptions (i) and (ii). Thus, the total energy consumption in the
proposed method is expected to be smaller than that of the 802.11 TSF.
160
: IEEE 802.11: proposed (threshold = 2)
: proposed (threshold = 1)
: proposed (threshold = 0)

140

number of nodes

120
100
80

rapidresynchronisation
syncbottleneck

6040
sync

20
00

1020

Initially, there are 143 nodes, and the number of nodes decreases
monotonically as the synchronisation proceeds. In the 802.11 TSF along bottleneck always emerges. In contrast, in the proposed method,such a bottleneck is reduced (þ; *, and u symbols in Fig. 3), where arapid resynchronisation emerges in several dozen nodes simultaneously,
leading to total resynchronisation. This rapid resynchronisation, which isa characteristic feature of the proposed method, is a byproduct ofmodifications (i) and (ii) above. A brief explanation of this mechanism
is as follows: (a) as the resynchronisation proceeds, the density of the
non-resynchronised nodes is gradually lowered; (b) for such a low nodedensity, BC becomes less competitive and modifications (i) and (ii) oftencause some of the nodes to remain awake simultaneously; and (c) in thiscase, if some of the nodes within another IBSS (s) transmit beacons,
then they are received by these non-resynchronised nodes, whereupon
resynchronisation is completed in a single beacon cycle.
Thus, the bottleneck reduction in the proposed method is realised bya kind of self-adaptive, rapid synchronisation process, which isachieved through a simple modification of the 802.11 TSF. The above
observation is also verified through a modified simulation protocol, as
per [3], including simplification factors (2) and (3) mentioned above.
We expect the proposed self-adaptive algorithm to be beneficial also in
the activity-scheduling problem in flooding algorithms [6], which is
now under investigation.
Acknowledgments: This work was partially supported by NICT andthe Ministry of Education, Science, Sports and Culture, Grant-in-Aid,
18560370 (2006), and stimulated by the activities of the AdHoc
Wireless Network Consortium.
# The Institution of Engineering and Technology 2006
4 May 2006
Electronics Letters online no: 20061390
doi: 10.1049/el:20061390
H. Tanaka, O. Masugata and D. Ohta (Department of ElectronicEngineering, The University of Electro-Communications (UEC),
1-5-1 Choufugaoka, Choufu-shi, Tokyo 182-8585, Japan)
A. Hasegawa and P. Davis (ATR Adaptive Communications ResearchLaboratories, 2-2-2 Hikaridai, Keihanna Science City, Kyoto
619-0288, Japan)
References
1 IEEE Std. 802.11 Wireless LAN Medium Access Control (MAC) andPhysical Layer (PHY) Specification, http://standards.ieee.org/getieee802/download/802.11-1999.pdf
2 Huang, L., and Lai, T.-H.: ‘On the scalability of IEEE 802.11 ad hoc
networks’. Proc. 2002 ACM Int. Symp. on Mobile Ad Hoc Networkingand Computing, pp. 173–182
3 Sheu, J.-P., Chao, C.-M., and Sun, C.-W.: ‘A clock synchronization
algorithm for multi-hop wireless ad hoc networks’. Proc. 2004 Int.
Conf. on Distributed Computing Systems, pp. 574–581
4 Hasegawa, A., and Davis, P.: ‘Long coalescence times for ad hoc cells
using 802.11 MAC protocol’. Proc. 2004 IEICE Spring Society Meeting,p. 407
5 Ohta, D., Tanaka, H., Hasegawa, A., and Davis, P.: ‘Timing-sync issues in
multi-hop networks using 802.11 MAC Protocol (2)’. Proc. 2005 IEICE
Fall Society Meeting, p. 460
6 Stojmenovic, I., and Wu, J.: ‘Broadcasting and activity scheduling inad hoc networks’ in ‘Mobile ad hoc networking’ (IEEE=Wiley, 2004),
pp. 205–229

sync304050time, s607080Fig. 3 Resynchronisation process

Bottleneck reduction mechanism: In this Section, we analyse thereduction of the synchronisation bottleneck in the proposed method,
and the observed efficiency is explained. Fig. 3 shows the number ofremaining, non-resynchronised nodes ( in Fig. 1) against time for thefour cases (þ, *, u and ) corresponding to the data shown in Fig. 2.

ELECTRONICS LETTERS 3rd August 2006 Vol. 42 No. 16