Abstract-Vehicular Ad Hoc Network (VANET) is a kind of special wireless ad hoc network, which has a high node mobility and fast topology changes. Clustering is a technique for grouping nodes together, making the network more robust. Clustering is an important research topic in wireless networks, because cluster structures can facilitate resource reuse and increase system capacity. Clustering has been found as a solution for VANET's high mobility. Also selecting the cluster head and maintaining the stability of the clustered VANET nodes are essential for better communication. Cluster stability and maintaining it, is an important goal that clustering algorithms try to achieve and it is considered as a measure of performance of a clustering algorithm, further selecting the proper cluster head is crucial to maintain the stability of the clustered network. To achieve, this paper propose a combination of bully algorithm and Lamport timestamp for selecting the better cluster head and also for Cluster head switching in an efficient way for better performance in the stability of VANET nodes. Index Terms-Clustering, cluster head, routing protocol, stability, VANET. In the last decade Mobile Ad Hoc networking (MANET) has become a very attractive topic among researchers. Numerous articles have been published with new solution proposals, extensions and improvements to existing methods and algorithms, including theoretical analysis of the problems involved with simulation results. The growth of the increased number of vehicles, which are equipped with wireless transceivers to communicate with other vehicles have formed a special class of wireless network known as Vehicular Ad-Hoc network (VANET) and VANET has become the key component of the Intelligent transportation systems (ITS) [1] . VANET is a special class of Mobile Ad hoc Network (MANET), to provide communication among nearby vehicles, between vehicles and nearby roadside equipments which commonly known as Infrastructure (I) or commonly known as Road side Units (RSU). VANETs do have dynamic topologies, they are not completely random [2] . The movement of a VANET node (vehicles are the nodes in the VANET environment) is relatively predictable because it is restricted to the roads on which the vehicles travel. Most of Manuscript received August 11, 2016; revised December 2, 2016. Pramodh Kavisha Dharmawardena is with Dalian University of Technology, Dalian, China (e-mail: pramodhshani@yahoo.com [6] nature of the VANET environment. However, when the number of nodes increases, with each node handling its own decentralized routing and neighborhood connectivity maintenance tasks, serious scalability and hidden terminal problems may occur. The most common solution adopted for this problem is clustering [7] . Clustering in VANETs aims to organize vehicles into groups based on some specific common characteristics. Using this technique can lead to more coordination of the nodes and less inter node interference. The clustering must be periodically updated to reflect topological changes and vehicle movements. Clustering within the network must be very fast to minimize time lost between the inter node communication. VANETs have to overcome some issues and challenges related to their specific characteristics, such as the very dynamic network topology related to the high velocity of vehicles, to ensure acceptable Vehicle to Vehicle communication (V2V) and Vehicle to Infrastructure (V2I) communication. Most of the solutions proposed to handle these issues are based on creating dynamic clusters to self organize the vehicular network where the dynamic clustering formation can be either in a decentralized or centralized way, further clustering is to group the nodes into homogeneous sets. Each cluster has one cluster head (CH) elected from the cluster members, which controls flows and signaling inside the cluster, particularly for V2I communications [8]-[10]. Typically, the members of one cluster have some common characteristics, e.g., near coordinates, velocities, same direction. Theory and Engineering, Vol. 9, No. 3, June 2017 218 DOI: 10.7763/IJCTE.2017.V9.1141 on the Lowest-ID algorithm but uses signal power levels and mobility metric derived from successive receptions instead. Its performance is moderate as it is not designed and optimized for VANET but it is frequently used for comparison with other VANET clustering solutions. The AMACAD [12] algorithm tries accurately to follow the mobility pattern of the network and prolong the cluster lifetime and reduce the global overhead. As the vehicle destination is the key factor in the algorithm, the metric of the clustering decision is based on the current location, speed and both relative and final destination. There might be a problem with knowing the final destination early as drivers usually do not use navigation system for known routes. Cluster size is a variable according to vehicle density, speed and required minimum bandwidth or QoS where parameters can be predefined or provided from vehicle sensors and application profiles. One of the rare multi-hop clustering solutions has been presented by Z. Zhang [13] and used relative mobility between multi-hop distant vehicles as the metric. Also it has used beacon (radio propagation) delay on each node, aggregated and propagated back to other nodes. Cluster head becomes the node with smallest aggregate mobility value. Cluster stability is also increased and unnecessary re-clustering time has been reduced when two cluster heads meet each other. The many challenges associated with VANETs provide ample motivation for a clustered network. VANETs suffer from the hidden terminal problem and have congestion issues caused by routing in the dense and highly mobile environment [14] , [15] . Although various Clustering methods been introduced to solve these obstacles, maintaining stability of the cluster has caused some serious issues, such as choosing the better Cluster Head (CH), performing efficient (CH) switching, end to end delay and message overloading. The main obstacle is to maintain cluster stability for the longest period; otherwise, the performance will be degraded due to frequent re-election and (CH) switching operations [16]-[18]. Bully algorithm is an efficient and simple electing algorithm, it can be implemented very simply and the computation time might be less, also if re-election is needed it can be implemented quickly. For election message system if we use a digital message system which contains needed data with a timestamp, not only it will be easier to elect the greater node, but also it will be efficient for re-electing, then the Cluster Head switching would be much more efficient. Lamport Timestamp is such kind of digital message system; message contains a time line with the message content and the message ID which is convenient for re-election. In the proposed system we have used the combination of Bully algorithm and Lamport timestamp and it is more efficient for selecting the Cluster Head in VANET Clustering and also to maintain the Cluster stability. In proposed work we have slightly changed the procedure of the Bully algorithm in a favorable way for the proposed system and it might reduce the election time and message over loading. Bully algorithm is the fastest among election algorithms, when any node notices that the coordinator (CH) is no longer responding to requests, it initiates an election. The node P holds an election as follows 1) P sends an ELECTION message to all processes with higher numbers. 2) If no one responds, P wins the election and becomes coordinator (CH). 3) If one of the higher-ups answers, it takes over. P's job is done. At any moment, a process can get an ELECTION message from one of its lower-numbered member nodes. When such a message arrives, the receiver sends an OK message back to the sender to indicate that it is alive and will take over. The receiver then holds an election, unless it is already holding one. Eventually, all nodes give up except one, and that one is the new coordinator. It announces its victory by sending all nodes a message telling them that starting immediately it is the new coordinator. If a process that was previously down comes back up, it holds an election. If it happens to be the highest-numbered process currently running, it will win the election and take over the coordinator's job [19] . In Fig. 1 we see an example of how the bully algorithm works. The group consists of eight processes, numbered from 0 to 7. Previously process 7 was the coordinator, but it has just crashed. Process 4 is the first one to notice this, so it sends ELECTION messages to all the processes higher than it, namely 5, 6, and 7 as shown in Fig. 1(a) . Processes 5 and 6 both respond with OK, as shown in Fig. 1(b) . Upon getting the first of these responses, process 4 knows that its job is over. It knows that one of these big nodes will take over and become coordinator. In Fig. 1(c) , both 5 and 6 processes hold elections, each process only sends messages to those processes higher than itself. In Fig. 1(d) process 6 tells process 5 that it will take over. At this point process 6 knows that process 7 is dead and process 6 takes over as the new coordinator (CH). The expression x-y is read "x" happens before "y" and means that all processes agree that first event "x" occurs, and then afterward, event "y" occurs. This happens-before relation can be observed directly in two situations: 1) If "x" and "y" are events in the same process, and "x" occurs before "y", then x-y is true. Theory and Engineering, Vol. 9, No. 3, June 2017 219 2) If "x" is the event of a message being sent by one process, and "y" is the event of the message being received by another process, then x-y is also true. A message cannot be received before it is sent, or even at the same time it is sent, since it takes a finite, nonzero amount of time to arrive. According to the Lamport timestamp each node in the network maintains a counter that functions as a clock. Each node has a digital identity, and the ability to pass information as a message [19] . The message format in Fig. 2  (Id, M, Ti) , Id is the node identification, M is the message content-thresh hold (TH) value and Ti is the timestamp. Eg: message X is from node i and message Y is from node j Ti<Tj or Ti=Tj, and i<j -Message X is earlier than the message Y. The next section explains the main scenario of the proposed system. *Src node sends (TH) value to all members in Lamport digital messages, in this proposed system all the messages are sent and received through Lamport digital messages, including ID, (TH) value and the timestamp.  International Journal of Computer According to the Fig. 3 , among the entire nodes, the first node to enter the zone will be chosen as the source node. When a node enters for the first time to the zone it will automatically send a message (Lamport modified) to the nearest infrastructure (I). Then the (I) will indicate the Id number for the node. If the Id=1 then the node will be the source node and in the mean time Clustering will begin and the source node will start sending the election messages according to the proposed system. As mentioned above, in the proposed system, we have changed the procedure of the Bully algorithm and used Lamport digital message system as the election messages. According to the original way of the Bully Theory and Engineering, Vol. 9, No. 3, June 2017 220 algorithm, the source node or the node which initiates the election messages, gives up its job after receiving OK messages from member nodes, and letting the suitable member nodes to choose the Coordinator (CH). But in our system, source node sends a Threshold Value ((TH) value which contains the vehicle's location, speed, destination, battery power and fuel consumption) to all member nodes. Then member nodes will compare their own (TH) value with the received (TH) value from the source node and reply if the own (TH) value is greater than source node's (TH) value. Once the source node receives replies from the member nodes, it sorts out the values according to the higher rank and sorts out the best and the second best (CH) and inform to the related nodes. According to the proposed system we can reduce the time consumption for electing the (CH) and message over load. Further, if re-election of (CH) or (CH) switching is needed, it can be done efficiently because source node has sorted out the second best (CH) while choosing the best (CH) and informed. The proposed system is shown in the flow diagram Fig. 3 and the main stages of cluster head selection are explained and mentioned in 3 states below. Further Fig. 4 illustrates the steps of the proposed system in algorithmic way (pseudo code of the proposed system). International Journal of Computer Once the node enters to the zone it gets its own Id number from the Infrastructure (I). Within every period of time T=t 1 , (I) will broadcast the Id=1 message to select the Source node (Src node) and within a time T=t 2 the cluster is formed. The node which gets the Id=1 will become the Source Node and remaining nodes become member nodes (illustrated in the Step 1 and Step 2 of Fig. 4) . Main idea of this research is to implement the Cluster Head selection, Src node will initiate the election and it will send its own Threshold value (TH) value in a Lamport Digital message to the member nodes. After receiving the (TH) value member nodes will compare the value with its own (TH) value and if its own (TH) value is higher than Src (TH) value, member node will reply OK with their (TH) value in a Lamport Digital massage (illustrated in the Step 3 and Step 4 of Fig. 4) . If not member node won't reply and remain as a member node. If Src node receives replies, Src node will sort out the best and the second best (CH) and inform them to the related nodes. If Src node won't receive any messages within a time T=t 3, Src node will become the CH (illustrated in the Step 5 of Fig. 4) . Because of choosing the second best (CH), the process of switching the (CH) or re-election of the (CH) can perform easily if needed. Also we can reduce the message flooding and the computation time of the Src node, further it will be easy to maintain the stability of the Cluster. In simulation we try to compare the proposed algorithm in cluster based routing with existing reactive based routing protocols. Proposed routing protocol is compared with endto-end throughput, end-to-end delay, and packet delivery ratio and energy consumption. The tool used to simulate the project is network simulator 2 (NS-2.31). Performance of proposed Cluster Based Routing is analyzed with aggregate network throughput, average packet delay and per packet energy consumption with respect to number of packets per second (or) data rate. Later, same performance metrics are analyzed with a number of mobile nodes within the network. Total numbers of mobile nodes are considered as 100. Total numbers of flows are considered as 50. During the simulation period, nodes have random mobility and total simulation period is considered as 50 Sec. Theory and Engineering, Vol. 9, No. 3, June 2017 221 Fig. 5(a) explains about end-to-end aggregate throughput (Kbps) with respect to data rate in VANET. From Fig. 5(a) it is clear that achievable aggregate throughput for cluster based routing protocol is better with existing AODV and DSR routing protocols. Fig. 5(b) explains about average end-to-end delay for 1024 byte data transmission in between source and destination. Fig. 5(c) explains about the aggregate throughput for 512 byte data. For 512 byte data the achievable aggregate throughput is less when compared with 1024 byte data. This is due to increased control overhead in 512 byte data in between source and destination. Fig. 5(d) explains about achievable end-to-end node average throughput with node energy consumption. Whenever the node transmission power is more, then the number of hops in between source to destination will be relatively less. This in-turn results in reduced control overhead and increased achievable throughput. But, increased node power consumption may lead to interference with member nodes which results in packet loss due to collisions. International Journal of Computer VANET is a special network type among the category of Ad-Hoc Networks. Due to the dynamic motion among the nodes and the high mobility environment, maintaining the network stability has created serious issues. Clustering has been introduced as a solution for the dynamic situation among the VANET nodes. But clustering also has issues on maintaining the network stability. The method this paper proposed is assumed to be a solution for selecting a better Cluster Head based on Bully algorithm with Lamport digital message system, if re-election or CH switching is needed it is easily managed, because source node sorts out the second best CH while choosing the best CH. It helps to maintain the network stability by choosing the better cluster head efficiently. In the simulation results we have showed that using this method in cluster based routing protocols, is much more efficient than AODV and DSR reactive protocols. He is a senior member of China Computer Federation and the director of AMD-SUN 64 bit technology application development center in Dalian University of Technology. He has completed more than 50 scientific research projects and more than 30 articles were published in the core journals. Associate Professor Wang has won two awards for scientific and technological progress in Liaoning province. He got the invention patents for Automatic transmission control system and control method of coal blending and for Multi robot system scheduling organization collaboration system, on
A combination of bulley and Lamport timestamp algorithm was presented for the cluster head selection in REF .
Cluster Head selection Based Routing Protocol for VANET Using Bully Algorithm and Lamport Timestamp
International Journal of Computer Theory and Engineering
Computer Science