Example of k-mean Clustering Algorithm Implementation on ns2

In some network simulations, we need to cluster nodes according to some parameters for getting an improved performance. For example, in most of the Wireless Sensor Network(WSN) related applications, we often make clusters of nodes to reduce the overhead in network-wide message delivery and to minimize the overall battery energy of the network.

There are so many ways to do this clustering. There are some ingenious “voting based” models to automate this clustering process and elect a cluster head.

But in this example, we outline some of the clustering ideas that can be used in the design of clustering that was controlled by a centralized management server. In other words, here we assume that a central server/node will know the locations of all the nodes in the network so that it can make clusters out of it. (it is assumed that the participating nodes will pass their location information to the server, or the server already knows the location of all the nodes during the node deployment phase itself)

Caution: The following are some code segments of a huge tcl simulation script. A major portion of the actual simulation events was intentionally omitted due to some privacy reasons. So one can not make it work as it is. But, one can understand the implementation of k-mean clustering and the CESAR Chipher based Encryption and decryption and make it work in their simulations.

Further, one should keep in mind that this kind of clustering implementation is only suitable for doing clustering using a centralized server. Automated Clustering and cluster head node(CH node) selection should be done only using some sophisticated, distributed algorithm that should be run on all the nodes of the network to handle CH election process and Cluster membership maintenance process on an ad-hoc basis – those aspects of clustering were not addressed in this article.

Important Sections of the Clustering Implementation Code

I hereby present some of the core parts of the clustering simulation

Setting Values of Some Parameters

###################################################################################################
## Implementing of Clustering on MANET ##
###################################################################################################

# Defining Some Important Simulation Parameters

set MESSAGE_PORT 42
set BROADCAST_ADDR -1

set BroadcastDelay 0.01 ;

set NamAnimationSpeed 250u ;#in Micro Seconds
set MessageSize 100 ;# in bytes Max 1500
set NodeVeocity 1 ; # meters per second
set SizeoftheNodes 10
set mobile 1 ;# 0 for static network 1 for mobile network

set NumberOfKeyChangeMessages 0
set KeyChangeMethod 0 ;# 0 for Normal 1 for Clustering

# variables which control the number of nodes and how they’re grouped
# (see topology creation code below)

set Number_of_Groups 4
set Nodes_Per_Group 10

set TotalNumberOfNodes [expr $Nodes_Per_Group * $Number_of_Groups]

set val(chan) Channel/WirelessChannel ;#Channel Type
set val(prop) Propagation/TwoRayGround ;# radio-propagation model
set val(netif) Phy/WirelessPhy ;# network interface type

#set val(mac) Mac/802_11 ;# MAC type
#set val(mac) Mac ;# MAC type
set val(mac) Mac/Simple

set val(ifq) Queue/DropTail/PriQueue ;# interface queue type
set val(ll) LL ;# link layer type
set val(ant) Antenna/OmniAntenna ;# antenna model
set val(ifqlen) 50 ;# max packet in ifq

#Selecting some simple Routing Protocol.
#since one hop routing is only required in the Clustering model, we use DumbAgent as routing agent

set val(rp) DumbAgent
# size of the topography -The ClusteringCoverage Range
set val(x) 400
set val(y) 400

Create Simulator Object and Configure Default Node Parameters

set ns [new Simulator]

set f [open Clustering-v2.tr w]
$ns trace-all $f
set nf [open Clustering-v2.nam w]

$ns namtrace-all-wireless $nf $val(x) $val(y)

$ns use-newtrace

# set up topography object
set topo [new Topography]

$topo load_flatgrid $val(x) $val(y)

create-god $TotalNumberOfNodes

set chan_1_ [new $val(chan)]

# Setting Default node Configuration

$ns node-config -adhocRouting $val(rp) \
-llType $val(ll) \
-macType $val(mac) \
-ifqType $val(ifq) \
-ifqLen $val(ifqlen) \
-antType $val(ant) \
-propType $val(prop) \
-phyType $val(netif) \
-topoInstance $topo \
-agentTrace ON \
-routerTrace ON \
-macTrace ON \
-movementTrace OFF \
-channel $chan_1_

Creating an Agent for ClusteringMessage Handling

Some Examples of Implementing Custom Functions of the ClusteringAgent

Function Send_Message_to_a_Node

Agent/ClusteringAgent instproc Send_Message_to_a_Node {size message_id data addrs port} {
$self instvar node_
global ns BROADCAST_ADDR BroadcastDelay

$self sendto $size “$message_id:$data” $addrs $port
}

Function Broadcast_Message_to_All

Agent/ClusteringAgent instproc Broadcast_Message_to_All {size message_id data port} {
$self instvar node_
global ns MESSAGE_PORT BROADCAST_ADDR BroadcastDelay rng
$ns trace-annotate “[$node_ node-addr] sending message $message_id”
set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]
$self sendto $size “$message_id:$data” $BROADCAST_ADDR $port
}

Function Multicast_Message_to_SubGroup

Agent/ClusteringAgent instproc Multicast_Message_to_SubGroup {size message_id data port} {
$self instvar node_
global ns MESSAGE_PORT BROADCAST_ADDR BroadcastDelay rng

$ns trace-annotate “[$node_ node-addr] sending message $message_id”
set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]
$self sendto $size “$message_id:$data” $BROADCAST_ADDR $port
}

Function SetItAsClusterManagementNode

Agent/ClusteringAgent instproc SetItAsClusterManagementNode {} {
$self instvar node_ CurrentGroupKey
global ns MESSAGE_PORT BROADCAST_ADDR BroadcastDelay rng

$node_ add-mark rr black circle
$node_ label Cluster
$self set IsClusterNode 1

# During Initialization, Randomly Create a Group Key.

set CurrentGroupKey [ expr [$rng integer 3 ] + 1 ]

set MessageID “LBCN” ;# Cluster Beacon Message
set Data “DummyData”
set TotalSize 15
#Periodically Broadcast a Beacon From Cluster Delivering Node to Broadcast its presence
set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]
$ns at [expr [$ns now] + $Jitter ] “$self Broadcast_Message_to_All $TotalSize $MessageID $Data $MESSAGE_PORT”
}

Function RegisterToCluster

Agent/ClusteringAgent instproc RegisterToCluster {ClusterId PublicKey} {
$self instvar node_
global ns MESSAGE_PORT rng

set MessageID “RFLR” ;# Register For Cluster Message
set Data PublicKey
set TotalSize 15

set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]

$ns at [expr [$ns now] + $Jitter ] “$self Send_Message_to_a_Node $TotalSize $MessageID $Data $ClusterId $MESSAGE_PORT”

}

Function RegisterTheClusterMemberAndSendGroupKey

Agent/ClusteringAgent instproc RegisterTheClusterMemberAndSendGroupKey {ClusterMemberNodeId} {
$self instvar node_ CurrentGroupKey
global ns MESSAGE_PORT rng

set MessageID “REGS” ;# Register For Cluster Message

set TotalSize 15
#Encrypt the Groupkey with ClusterMember’s Public Key ( Here the Public Key of the ClusterMember is Just its ID)
#And Encryption is Just a sum of Group Key and ClusterMember’s Public Key

set EncryptedGroupKey [expr $CurrentGroupKey + ( $ClusterMemberNodeId % 10 ) ]

#send Registration Message three times to ensure delivery

set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]
$ns at [expr [$ns now] + $Jitter ] “$self Send_Message_to_a_Node $TotalSize $MessageID $EncryptedGroupKey $ClusterMemberNodeId $MESSAGE_PORT”

}

Function SendMessageToRegisteredClusterMembers

Agent/ClusteringAgent instproc SendMessageToRegisteredClusterMembers {} {
$self instvar node_ CurrentGroupKey
global ns MESSAGE_PORT BROADCAST_ADDR BroadcastDelay rng

set MessageID “MESG” ;# Register For Cluster Message
set Data “SECRET MESSAGE”
#Here we encrypt the data with the group key
set EncryptedData [$self Encrypt $Data $CurrentGroupKey ]
set TotalSize 100 ;# The size may be increased to simulate the real payload

set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]
$ns at [expr [$ns now] + $Jitter ] “$self Broadcast_Message_to_All $TotalSize $MessageID $EncryptedData $MESSAGE_PORT”
}

Function MemberSendMessageToServer

Agent/ClusteringAgent instproc MemberSendMessageToServer{ClusterId} {
$self instvar node_
global ns MESSAGE_PORT rng

set MessageID “ANSS” ;# Register For Cluster Message
set AnswerID [$node_ node-addr]
set Data “SampleData”
set TotalSize 100
#Here we have to encrypt the data with the public key of the node – It can be done latter
#the key sould be small to avoid non printable or invalid character in the string so the node id is devided by 20
# So few nodes will use same private key – it may be improved
set EncryptedAnswer [$self Encrypt $Data [expr [$node_ node-addr]/20 +1 ] ]

set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]
$ns at [expr [$ns now] + $Jitter ] “$self Send_Message_to_a_Node $TotalSize $MessageID $EncryptedAnswer $ClusterId $MESSAGE_PORT”

}

Function UnRegisterFromCluster

Agent/ClusteringAgent instproc UnRegisterFromCluster {ClusterId} {
$self instvar node_
global ns MESSAGE_PORT rng

set MessageID “URFL” ;# Register For Cluster Message
set Data $ClusterId
set TotalSize 15
set Jitter [expr ([$rng integer 100]+1.0 )/1000.0]
$ns at [expr [$ns now] + $Jitter ] “$self Send_Message_to_a_Node $TotalSize $MessageID $Data $ClusterId $MESSAGE_PORT”

puts “\nNode [$node_ node-addr] is sending Unregister Message to Cluster $ClusterId”
$ns trace-annotate “Node [$node_ node-addr] is sending Unregister Message to Cluster $ClusterId”
}

Implementation of k-Mean Clustering Algorithm

Implementation of CESAR Cypher Encryption

Implementation of CESAR Cypher decryption

Scheduling the evens for Simulation

$ns at .4 “$KMCAgent(0) SetItAsClusterManagementNode”

$ns at .5 “$KMCAgent(0) FindAllLocationsUsingGPSInfo”

$ns at .5 “$KMCAgent(1) FormSubGroupClusters $Number_of_Groups”

set ClusterId 0

for {set i 1} {$i < $TotalNumberOfNodes} {incr i} {

set MyPublicKey $i
$ns at 1.$i “$KMCAgent($i) RegisterToCluster $ClusterId $MyPublicKey”
}

$ns at 3 “$KMCAgent(0) SendTutorialsToRegisteredClusterMembers”

$ns at 10 “$KMCAgent(0) SendQuestionsToRegisteredClusterMembers”

set NormalResult 0
set ClusteringResult 0

Bar Chart for Performance Evaluation

#Prepare Bar Chart for Performance Evaluation

set fp [open TotalKeyChangeTransmissions.dat w]

puts $fp “TitleText: The Comparison of Total Network-wide Message Transmissions “
puts $fp “BarGraph: true”
puts $fp “BarBase: 0.0”
puts $fp “BarWidth: 1”
puts $fp “NoLines: true”
puts $fp “YUnitText: TotalKeyChangeTransmissions”
puts $fp “XUnitText: Method”
puts $fp “\”NormalMethod\””

$ns at 30 TestNormal
$ns at 60 TestClustering

$ns at 100.0 “finish”