Information Technology Reference
In-Depth Information
Figure 2. Neighbor discovery process
the biggest among its two-hop neighbors it wins
the channel. Otherwise, it chooses the channel in
which it has obtained its max hash. Then, it broad-
casts this information to its two-hop neighbors.
The RBSA algorithm has the following structure:
Let Hash( x ) be a fast message digest generator.
C max : number of channels, V 2 : two-hop neighbors,
α a node, C α : the channel number affected to α
and '⊕' is the concatenation of two operands.
derive the priority, denoted by H i , for node i and
contention context t i
H i = Hash (i ⊕ t i ) ⊕ i, where t i = (c i ⊕ s i )
(1)
Where the function Hash is a fast message
digest generator like MD4 or MD5 that returns a
random integer in a predefined range, and the sign
'⊕' is the concatenation of two operands. Note
that, although the Hash function can generate the
same number on different inputs, each number is
unique because it is appended with the identifier
of the node. The set of contexts is showed by the
following matrix || T || C * S .
A node α wins the slot t ij = (c i s j ) if it has the
highest hash value, i.e. the inequality presented
below must be verified for a node α, and that the
H i are calculated using the equation (2):
c. Slot Allocation Algorithm SBSA
The Sender Based Slot Assignment (SBSA) is
also an implicit consensus algorithm. Each node
is assigned a set of transmission slots of which it
will become the owner. Thus, the node will have
the highest priority to send during these slots.
SBSA works in the same way as RBCA where a
node determines for each channel its slot using
the distributed election algorithm. We denote the
set of contenders of an entity i by M i , and thus
its contention context by t i = (c i, , s i ) , where c i is
the channel i and s i is the slot i in channel i . To
decide the leadership of an entity without incurring
communication overhead among the contenders,
we assign each node a priority that depends on
the identifier of the node and the current conten-
tion context. Equation (1) provides a formula to
argmax H i = α
i ∈ M i ∪ { α }
(2)
argmax provides the argument of the maximum,
that is to say, the value of the given argument for
which the value of the given expression reaches
its maximum value. The SBSA algorithm has the
following structure:
Search WWH ::




Custom Search