Proposition et simulation d'un algorithme de partage de ressources dans les manets basé sur l'algorithme de Naimi et Tréhel

Bibliographie

[WCM02] J Walter, G Cao, and M. Mohanty. A k mutual exclusion algorithm for wireless ad hoc networks. Dans IEEE ISCC'02., 2002. (Cité page 14.)

[WK97] J.E. Walter and S. Kini. Mutual exclusion on multihop, mobile wireless networks.

Texas A and M University College Station, 1997. (Cité pages 13 et 14.)

[WW01] J. WALTER and L. WELCH. A mutual exclusion algorithm for ad hoc mobile networks. Department of Computer Science,Texas USA, 2001. (Cité page 13.)

ANNEXE : SCRIPT DE SIMULATION A

SOMMAIRE

A.1 LE SCRIPT TCL 50

# ===============================================================================
# Definition des options #
# ===============================================================================

set val(chan) Channel/WirelessChannel ;# type de canal

set val(prop) Propagation/TwoRayGround ;# model de propagation

set val(netif) Phy/WirelessPhy ;# type d' interface reseau

set val(mac) Mac/802_11 ;# type d' interface mac

set val(ifq) CMUPriQueue ;# type de la file d' attente

set val(ll) LL ;# link layer type

set val(ant) Antenna/OmniAntenna ;# model d' antenne

set val(x) 500 ;# X dimension du topology

set val(y) 500 ;# Y dimension du topology

set val(ifqlen) 50 ;# Nbre max des Packets -> file

set val(seed) 0.0 ;# grain random

set val(adhocRouting) DSR ;# protocole de routage

set val(sc) "/home/sami/ns-allinone-2.32/ns-2.32/ t c l /mobility/scene/modele " set val(stop) 20 ;# temps de simulation ( duree )

#=============================================================================== # Definition des procedures #

#===============================================================================

#Phy/WirelessPhy	set	RXThresh_ 1.92278e-06 ;	#10	meters
#Phy/WirelessPhy	set	RXThresh_ 7.69113e-08 ;	#50	meters
#Phy/WirelessPhy	set	RXThresh_ 3.00435e-08 ;	#80	meters
#Phy/WirelessPhy	set	RXThresh_ 1.42681e-08 ;	#100	meters
#Phy/WirelessPhy	set	RXThresh_ 8.91754e-10 ;	#200	meters
#Phy/WirelessPhy	set	RXThresh_ 1.76149e-10 ;	#300	meters
#Phy/WirelessPhy	set	RXThresh_ 5.57346e-11 ;	#400	meters

# modification dans la portee de signal 200 meters Phy/WirelessPhy set RXThresh_ 8.91754e-10

# ==============================================================================
# Creation d' instance de simulateur et topologie #
# ==============================================================================

set ns_ [new Simulator] ;# nouvelle simulation

$ns_ use-newtrace ;# nouveau f i c h ie r trace

set topo [new Topography] ;# Nouvelle Topologie

# ==============================================================================
# Creation des f i c h ie rs trace pour NS et NAM #
# ==============================================================================

set tracefd [ open adhoc.tr w]

set namtrace [ open adhoc.nam w]

set bw nbr_msg_tps.txt ;# Ficher . t x t ( resultat simulation )

set mesure [ open $bw w]

$ns_ trace-all $tracefd

$ns_ namtrace-all-wireless $namtrace $val(x) $val(y)

# ============================================================================== # Procedure d' affichage concernant la simulation # # ============================================================================== proc Affichage { } {

global mesure nbr nbracine nbrequete ;# Declaration des variables globales puts $mesure " "

puts $mesure " Les Resultats de la Simulation . "

puts $mesure " " puts $mesure "============= Informations de Simulation ============" puts $mesure " . " puts $mesure "Le Nombre de Sites = $nbr "

puts $mesure "Le Nombre de Racines R = $nbracine "

puts $mesure "Le Nombre de Requetes = $nbrequete "

puts $mesure " . "

puts $mesure "====================================================="

A.1 LE SCRIPT TCL

puts $mesure "================================="

puts $mesure " Resultas pour chaque site : "

puts $mesure "================================="

}

# ============================================================================== # Procedure de Terminaison de la simulation # # ============================================================================== proc finish { } {

global ns_ nf f0 nbr nbrequete tpatt nmsg p mesure ;# Variables globales for { set i 0} {$i < $nbr} { incr i} {

set nmsg [ expr [$p($i) set nb_message_]+$nmsg] ;# Somme des messages

}

puts $mesure "======================================================" puts $mesure " Le NMM et le TAM. "
puts $mesure "======================================================" puts $mesure " Messages total = $nmsg" ;# Calcul du nombre moyen des msg

puts $mesure " "

puts $mesure "Le NMM = $nmsg/$nbrequete = [ expr $nmsg/$nbrequete ] " puts $mesure " "

set tpatt [ expr $tpatt/$nbrequete] ;# Calcul du TAM

puts $mesure "Le TAM = $tpatt " ;# Affichage du TAM

$ns_ flush-trace ;# Ecriture dans le f i c h ie r TEXT

close $mesure ;# Fermer le fi c h ie r des resultat

puts " running nam... " ;# Affichage de "Running NAM . . . "

exec nam adhoc.nam & ;# lancer le NAM automatiquement

exit 0 ;# Sortie de la procedure

}

# ============================================================================== # Procedure d' enregistrement des temps d' attente dans le fi c h ie r . t x t # # ============================================================================== proc record {p n mutex hour} {

global f0 nbrequete tpatt mesure ;# Variables globales

set ns [Simulator instance] ;# Instancier la commande NS

set bw0 [$ns now] ;# bw0 est le temps actuelle

set bw0 [ expr $bw0- [$p set dem ] ] ;# bw0 := bw0 - Temps de la demande

puts $mesure "Temps d' attente pour le site N [ $n node-addr] =

$bw0 ==> ( ( Date_Requete = $hour ** Duree SC = $mutex ) ) " puts $mesure " "

set tpatt [ expr $tpatt+$bw0] ;# Le temps d' attente

}

# ============================================================================== # Procedure de Diffusion des demandes d' entrer en Section Critique # # ============================================================================== proc diffusion {p n mutex hour} {

global nbr ;# Variables globales

set ns_ [Simulator instance] ;# Instancier la commande NS

set nowe [$ns_ now] ;# Le temps actuelle

set nbrk [$p set nbracine] ;# nbrk := nbracine ;

$ns_ at $nowe " tester $p $n $mutex $hour" ;# execution de tester

$ns_ at $nowe "$p demander-sc" ;# execution de demander-sc

$ns_ trace-annotate " [ $n node-addr] demande la SC " ;# noeud demandeur

}

# ============================================================================== # Procedure de test d' entrer et la liberation de la Section Critique # # ============================================================================== proc tester {p n mutex hour} {

global nbr mesure ;# Variables globales

set ns_ [Simulator instance] ;# definir commande ns_

set time 0.01 ;# Temps de test pour SC

set now [$ns_ now] ;# Definir now

set a [$p set sc] ;# Affectation a := sc ;

i f { $a == 1} { ;# Condition entrer en SC

$ns_ at $now " record $p $n $mutex $hour" ;# Record pour le TAM

$ns_ at $now "$n label \"<SC> \" " ;# l i be le <SC> au noeud

$ns_ at [ expr $now+$mutex] "$n label \" \" " ;# Effacer <SC>

$ns_ at [ expr $now+$mutex] "$p liberation--sc";# Appel de liberation--sc

$ns_ at [ expr $now+$mutex] "$p set sc --1" ;# sc := --1 pour s o rt ir

} else { ;# noeud veut entrer SC

$ns_ at [ expr $now+$time] "$p attendre " ;# attendre MAJ sc <-- 1

$ns_ at [ expr $now+$time] " tester $p $n $mutex $hour"

}

}

# ============================================================================== # Procedure d' initialisation de la simulation et coloration # # ============================================================================== proc reaa {p n} {

set ns_ [Simulator instance] ;# definir commande ns_

set now [$ns_ now] ;# Le temps actuelle

$ns_ at $now "$p liaison" ;# appeler la procedure ( liaison)

$ns_ at $now " colorOr $p $n" ;# Coloration des racines

}

# ============================================================================== # ============================================================================== # Le programme Principale # # ============================================================================== # ============================================================================== # ============================================================================== # Lecture des donnees a partir d'un f ic h i er texte # # ==============================================================================

set f [ open " les_demandes.txt " " r " ] ;# lire ( les_demandes.txt )

set nbr [ gets $f] ;# ( nbr ) <-- premier ligne

set nbracine [ gets $f] ;# ( nbracine ) <-- deuxiemme ligne

set nbrequete [ gets $f] ;# ( nbrequete ) <-- troisiemme ligne

for { set j 0} {$j < $nbrequete} { incr j} { ;# Boucle pour lire les Scenarios for { set k 0} {$k < 2} { incr k} {

set table($j,$k) [ gets $f] ;# Remplir par ( site, heur )

}

}

close $f

# ============================================================================== # Declaration des couleurs selon les numeros # # ============================================================================== $ns_ color 0 Blue ;# Le O est la Couleur Bleu ( tous les messages) # ============================================================================== # Definition de la topologie # # ============================================================================== $topo load_flatgrid $val(x) $val(y)

# ============================================================================== # Creation du God ( voisinage ) # # ============================================================================== set god_ [create-god $nbr]

# ==============================================================================
# Configuration globale d'un noeud #
# ==============================================================================

$ns_ node-config -adhocRouting $val(adhocRouting) \

-llType $val(ll) \

-macType $val(mac) \ -ifqType $val(ifq) \ -ifqLen $val(ifqlen) \ -antType $val(ant) \ -propType $val(prop) \ -phyType $val(netif) \

-channelType $val(chan) \ -topoInstance $topo \ -agentTrace ON \

-routerTrace ON \

-macTrace OFF

# ============================================================================== # Creation des noeuds et des agents # # ============================================================================== for { set i 0} {$i < $nbr} { incr i} {

set node_($i) [$ns_ node]

$node_($i) random-motion 0

$node_($i) color Black

$god_ new_node $node_($i)

set p($i) [new Agent/Fifthalgo]

$p($i) set nb_noeud_ $nbr

$p($i) set nbracine $nbracine

$ns_ at 0.0 "$p ( $i ) initialisation"

$ns_ attach-agent $node_($i) $p($i)

$p($i) set packetSize_ 1024

}

# ============================================================================== # La connexion des agents pour permettre la communication # # ============================================================================== for { set i 0} {$i < $nbr} { incr i} {

for { set j [ expr $i+1]} {$j < $nbr} { incr j} {

$ns_ connect $p($i) $p($j)

} }

# ============================================================================== # Coloration des noeuds a chaque couleur associe # # ============================================================================== proc coloration {p node_ } {

set ns_ [Simulator instance]

set nowe [$ns_ now]

set a [$p set father]

set b [$p set nbjeton]

set c [$p set sc]

set d [$p set numrequest]

i f {$a == -1} {

i f {$b > 0} {

$ns_ at $nowe "$node_ color Orange"

}

} else {

$ns_ at $nowe "$node_ color Black"

}

i f {$d == 1} {

$ns_ at $nowe "$node_ color Limegreen"

}

i f {$c == 1} {

$ns_ at $nowe "$node_ color Red"

} } # ==============================================================================

# Appel des f i c hi e rs de mouvement #

# ==============================================================================

i f { $val(sc) == " " } {

puts " *** NOTE: no connection pattern specified. "

set val(sc) "none"

} else {

puts " Loading connection pattern..."

source $val(sc)

}

# ==============================================================================
# Initialisation des variables globaux #
# ==============================================================================

set nmsg1 0 ;# Initialisation de nmsg1

set nmsg 0 ;# Initialisation de nmsg

set tpatt 0 ;# Initialisation de tpatt

# ============================================================================== # Fixation de la duree de la Section Critique # # ============================================================================== set duree 1 ;# la duree de la Sc

# ============================================================================== # Initialisation des positions des noeuds # # ============================================================================== for { set i 0} {$i < $nbr} { incr i} {

$ns_ initial_node_pos $node_($i) 50 ;# se fait apres la definition

} ;# du modele de mobilite

# ============================================================================== # Initialisation et coloration des noeuds # # ============================================================================== for { set i 0} {$i < $nbracine} { incr i} {

$ns_ at 0.0 " reaa $p ( $i ) $node_ ( $i ) "

}

# ============================================================================== # Affichage du Menu dans le f i c hi e r des resultats #

# ============================================================================== $ns_ at 0.0 " Affichage " ;# Appel a la procedure Affichage

set ns_ [Simulator instance]

set nowe [$ns_ now]

# ============================================================================== # Coloration des noeud selon leur etat actuelle # # ============================================================================== for { set i 0} {$i < $nbr} { incr i} {

set temps 0.0

for { set j 0} {$j < 2000} { incr j} {

set temps [ expr $temps+0.01]

$ns_ at $temps " coloration $p ( $i ) $node_ ( $i ) "

}

}

# ============================================================================== # L' execution des scenarios de la simulation # # ============================================================================== for { set j 0} {$j < $nbrequete} { incr j} { ;# lire les Scenarios de la table

set site $table($j,0) ;# lire l ' identificateur du site

set heure $table($j,1) ;# lire l ' heur de la demande

$ns_ at $heure "$p ( $site ) set sc 0" ;# sc <- 0

$ns_ at $heure "$p ( $site ) set dem $heure " ;# aff ec ter la demande a l ' heur $ns_ at $heure " diffusion $p ( $site ) $node_ ( $site ) $duree $heure "

puts " $site" ;# Appel de diffusion pour

} ;# afin d' executer les demandes

# ============================================================================== # Finalisation de la simulation et debut du RUN # # ============================================================================== $ns_ at [ expr $val(stop) + 0.01] " finish";# Finir la Simulation apres (STOP)

puts " debut de la simulation .. . " ;# Ecrire " debut de la simulation.. "

$ns_ run ;# Debut du NAM

le Script TCL (Réseau AD HOC)