25-06-2013, 12:34 PM
FPGA Implementation of Cluster Formation Algorithms in Mobile Ad-hoc Networks
FPGA Implementation of Cluster.pdf (Size: 2.88 MB / Downloads: 38)
Abstract
Scalability has been an important issue in mobile ad-hoc
network (MANET). Clustering is one of the mechanisms that
are used in handling the scalability issue. Many cluster
formation and cluster maintenance algorithms have been
proposed for MANET. This paper presents the hardware
implementation and study of some of the proposed cluster
formation algorithms such as lowest ID, highest degree, Kclutstering,
and weighted clustering algorithm (WCA). The
FPGA implementation shows that for all four clustering
algorithms implemented, the CLB slices used is between 123
slices and 559 slices with operating frequency between
13 7.95 MHz and 325.5 MIHIz. For the same algorithms
implemented, the total power consumption is between 667.5
mW and 795.4 mW while the total current consumption is
between 329.2 mA and 401.3 mA.
INTRODUCTION
Mobile Ad-Hoc Network (MANET) is a connected
autonomous system of mobile nodes which are connected in a
wireless manner. The goal of MANET is to provide a robust
and efficient mobile wireless network in the environment
where fixed network is not possible to be installed (for
example at the battlefield or at the sea). All nodes in MANET
are free to move in random manner. Due to the mobility of
the nodes, the network topology may change rapidly. This
change will affect the connectivity among the nodes in the
network. In a rapidly changing network topology, managing
routing information will be difficult. Clustering is commonly
used in order to limit the amount of routing information
stored and maintained at each node. At the same time it also
reduces the channel resource utilization since the update of
routing information are carried out only for nodes within the
cluster. Clustering algorithm consists of cluster formation and
cluster maintenance phases.
FPGA IMPLEMENTATION
Implementation was carried out in the bottom-up fashion.
Module in the lowest level of the top-down design diagram
(Figure (2)) is implemented and tested first while module in
the top level is the last module to be implemented and tested.
Each module is implemented in VHDL, tested using test
bench, simulated and verified using ModelSim software
package. A buffer can contain up to 8 messages. The message
consists of an opcode and one or more operands. An opcode
identifies the message type while operand contains the
parameters needed for a certain type of message. Bits used in
opcode are different for each algorithm while bits used in
operand are the same which is 8 bits. Lowest ID uses 3 bits
for opcode and has I operand. The total bits used for the
buffer is 88 (8*(8+3)). Highest degree also uses 3 bits for the
opcode, but it has 3 operands hence the total bits used for the
buffer is 216 (8*(8*3+3)). K-clustering uses 4 bits for the
opcode and has 6 operands.
CONCLUSIONS
The main purpose of this paper is to compare the hardware
complexity and power consumption of various cluster
formation algorithms. Both hardware complexity and power
consumption analysis indicate that lowest ID algorithm
performs better than the other algorithms. Besides the
hardware complexity and power consumption analysis, we
also need to consider the network lifespan of each algorithm.
Algorithms that have a cluster head such as lowest ID, highest
degree and WCA have a large burden on cluster heads. Since
cluster head will be responsible for managing all the other
nodes, cluster head will run out of power quickly. While in
algorithm such as K-clustering, the cluster does not have a
cluster head hence nodes in the cluster have a longer lifespan
compared to the node that acts as cluster head in other
algorithms.