Approximating Size of Maximal Clique in a Node´s Neighbourhood in the Ad Hoc Networks

Author

Borovina, Nihad ; Kreso, Sead

Author_Institution

Fac. of Electr. Eng., Univ. of Sarajevo, Sarajevo

fYear

2009

fDate

5-8 April 2009

Firstpage

1

Lastpage

6

Abstract

This paper presents an algorithm for approximating the size of the maximal clique containing a given node in the ad-hoc network. The size of the maximal clique of a node can be used while deciding whether or not the node will be a part of a virtual backbone. An algorithm is distributed, based on 2-hop neighbourhood information, and works in O(Delta⁵) time, where Delta is the maximum node degree in the node´s neighbourhood. The simulation results show that the algorithm makes an accurate result in over 95% cases for the maximal clique consisting of up to 10 nodes. In many cases the structure of a clique can be identified.

Keywords

ad hoc networks; approximation theory; 2-hop neighbourhood information; ad hoc networks; maximal clique; node neighbourhood; virtual backbone; Ad hoc networks; Approximation algorithms; Communications Society; Euclidean distance; Mobile ad hoc networks; NP-complete problem; Peer to peer computing; Pricing; Resource management; Spine;

fLanguage

English

Publisher

ieee

Conference_Titel

Wireless Communications and Networking Conference, 2009. WCNC 2009. IEEE

Conference_Location

Budapest

ISSN

1525-3511

Print_ISBN

978-1-4244-2947-9

Electronic_ISBN

1525-3511

Type

conf

DOI

10.1109/WCNC.2009.4917601

Filename

4917601