2.3 NETWORK ASSUMPTIONS AND PRELIMINARIES
In this chapter, we assume that an ad hoc network comprises a group of nodes communicating with the same transmission range. Scheduling of transmission is the responsibility of the MAC layer. Each node has a unique ID and each node knows the ID and degree of its neighbors, which can be achieved through periodically broadcasting “HELLO” messages by each node. Since the emphasis of this chapter is on the CDS formation, we do not consider the node mobility. We call the nodes in the dominating set dominators, the nodes not in the dominating set dominatees, and the nodes that connect two or three hops away dominators connectors. Especially, we call the connectors that connect dominators two and three hops away one-hop connector and two-hop connector, respectively. Next, we give some well-known preliminaries.
Preliminary 2.1. By building a dominating set through MIS construction, for every node u, the number of dominators inside the disk centered at u with radius k-unit is bounded by a constant lk.
Proof. Alzoubi et al. gave a proof through calculation of lk < (2k + 1)2 − 1 [15]. When k = 2, 3, we have lk = 23, 47. Recently, Li et al. have proved that l3 = 42 [16].
Preliminary 2.2. Let G be a UDG and opt be the size of a minimum CDS for G, then the size of any MIS for G is at most 3.8 × opt + 1.2.
The proof of this preliminary bounds the size of any MIS in G and can be found in Ref. [9].
Preliminary 2.3. In a DS, the maximum distance to another ...
Get Mobile Intelligence now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
