Index: nodes/channelga.ml =================================================================== --- nodes/channelga.ml (revision 1991) +++ nodes/channelga.ml (revision 1993) @@ -19,4 +19,6 @@ - on node x, interfaces y and z are well separated and can live on the same channel + - the link between x on y and z on w is very important, make sure it is + well separated on both ends of the link - interface x on node y will bother interface z on node w and need to be on separate channels @@ -45,7 +47,12 @@ (** How long should the system iterate after an improvement? *) and max_stagnant_iterations = 2000 -(** What is the chance for an ESSID to channel assignment to mutate to a +(** What is the chance for an ESSID-to-channel assignment to mutate to a random channel? *) -and mutation_rate = 0.1;; +and mutation_rate = 0.1 +(** The most basic score table *) +and scoretable = [ ((<=) 2, 1); + ((==) 2, -30); + ((==) 1, -70); + ((==) 0, -100) ] (* the type definitions. note that Caml has trouble with mutually recursive @@ -79,12 +86,18 @@ let groups = Hashtbl.create 4 +(* Now the hashes for the special cases *) +(** Hash mapping from nodename to a list of winame's indicating the wi's that + don't interfere with eachother for the given node *) let nointerference = Hashtbl.create 4 +(** List of (nodename1, winame1, nodename2, winame2) tuples indicating a very + important link that should be well-separated on both ends *) +let importantlinks = ref [] +(** Hash mapping from nodename to a list of unusable channels for that node *) let unusable = Hashtbl.create 4 -let interference = [] - -let scoretable = [ ((<=) 2, 1); - ((==) 2, -30); - ((==) 1, -70); - ((==) 0, -100) ] +(** List of (nodename1, winame1, nodename2, winame2) tuples indicating two + interfering interfaces on different nodes *) +let interference = ref [] + +(** Run the given diff against the given scoretable and return the score *) let rec runtable t diff = match t with @@ -114,6 +127,8 @@ let copyarray src dest = Array.blit src 0 dest 0 (Array.length src) -let in_list l i = try - let _ = List.find ((==) i) l in +(** Is the given element in the given list? uses compare, so it works on + strings as well *) +let in_list l e = try + let _ = List.find (fun x -> (compare e x) == 0) l in true with Not_found -> false @@ -133,5 +148,6 @@ let is_unusable = in_list unusable in if (is_unusable channel1) || (is_unusable channel2) then -10000 - else if in_list nointerference (maketuple wi1 wi2) then 1 + else if (in_list nointerference wi1.wi_name) && + (in_list nointerference wi2.wi_name) then 1 else runtable scoretable diff;; @@ -148,58 +164,24 @@ base_score * (List.length n.node_wis) -let test_interference c (wi1, wi2) = +(** Score the given pair of interferent interfaces against the given + configuration *) +let score_interference c (nodename1, winame1, nodename2, winame2) = + let wi1 = List.find (fun wi -> (compare wi.wi_name winame1) == 0) (Hashtbl.find nodes nodename1).node_wis in + let wi2 = List.find (fun wi -> (compare wi.wi_name winame2) == 0) (Hashtbl.find nodes nodename2).node_wis in let channel1 = c wi1.wi_essid in let channel2 = c wi2.wi_essid in let diff = abs (channel1 - channel2) in - runtable scoretable diff + let res = runtable scoretable diff in + res (** Given a list of nodes and a configuration, return the score for the whole - configuration. This is the sum of the scores for all nodes. *) + configuration. This is the sum of the scores for all nodes, plus the sum + of the scores for all user-specified interferent pairs of interfaces. *) let score_configuration ns c = let mapper = Hashtbl.find c in let foldfunc acc n = acc + (node_score mapper n) in let nodescores = List.fold_left foldfunc 0 ns in - let interference_penalty = List.fold_left (fun a i -> a + test_interference mapper i) 0 interference in - nodescores + interference_penalty;; - -(** Given a filename, return a list of all the lines in the file with the given - filename. Don't count on the order of the lines in the result. *) -let snarf_lines fname = - let infile = open_in fname in - let result = ref [] in - try - while true do - result := (input_line infile)::!result - done; - !result (* never gets here *) - with End_of_file -> !result - -(** Given the name of the node currently being parsed, parse the given tuple - that consists of a wi name and an essid. *) -let parse_pair nodename (wname, essid) = - let new_wi = { wi_name = wname; wi_nodename = nodename; wi_essid = essid} in - let foo = try - let group = Hashtbl.find groups essid in - group.group_wis <- new_wi::group.group_wis; - with Not_found -> - let group = { group_essid = essid; group_wis = [ new_wi ] } in - Hashtbl.add groups essid group in - new_wi - -let parse_fields fields = - let nodename = head fields in - let rec makepairs l = match l with - [] -> [] - | x::[] -> assert false - | a::b::xs -> (a, b)::(makepairs xs) in - let wis = List.map (parse_pair nodename) (makepairs (tail fields)) in - let sorted_wis = List.sort compare wis in - let node = { node_name = nodename; node_wis = sorted_wis } in - Hashtbl.add nodes nodename node - -let parse_file fname = - let spacere = Str.regexp " " in - List.iter (parse_fields $ (Str.split spacere)) (snarf_lines fname) - ;; + let interference_score = List.fold_left (fun a i -> a + score_interference mapper i) 0 !interference in + nodescores + interference_score;; (** Return a random configuration. For some reason, if this function accesses @@ -216,21 +198,4 @@ let sorted_nodes = List.sort (fun a b -> compare (a.node_name) (b.node_name)) (values nodes) in List.iter (fun n -> print_string (n.node_name ^ ":" ^ (wis n) ^ "\n")) sorted_nodes - -let parse_nodeclusters fname = - let spacere = Str.regexp " " in - (* handle a row of fields. the first field is the supernode name, the - rest are the subnode names. create a new node for the supernode, - stuff all the wi's of the subnodes under it, names prefixed with - their original node's names for clarity, and remove the subnodes - from the nodes hashtable *) - let do_fields f = let nodename = head f in - let subnodenames = tail f in - let subnodes = List.map (Hashtbl.find nodes) subnodenames in - List.iter (Hashtbl.remove nodes) subnodenames; - let prefixed_wis n = List.map (fun w -> { w with wi_name = n.node_name ^ "." ^ w.wi_name}) n.node_wis in - let wis = List.fold_left (fun a s -> a@(prefixed_wis s)) [] subnodes in - let node = { node_name = nodename; node_wis = wis } in - Hashtbl.add nodes nodename node in - List.iter (do_fields $ (Str.split spacere)) (snarf_lines fname);; (** Generalized evolutionary algorithm driver. @@ -269,7 +234,88 @@ population.(0);; +(** BEGIN PARSING CODE *) + +(** Given a filename, return a list of all the lines in the file with the given + filename. Don't count on the order of the lines in the result. *) +let snarf_lines fname = + let infile = open_in fname in + let result = ref [] in + try + while true do + result := (input_line infile)::!result + done; + !result (* never gets here *) + with End_of_file -> !result + +(** Read the main input from the given filename *) +let parse_file fname = + let spacere = Str.regexp " " in + (** Given the name of the node currently being parsed, parse the given tuple + that consists of a wi name and an essid. *) + let parse_pair nodename (wname, essid) = + let new_wi = { wi_name = wname; wi_nodename = nodename; wi_essid = essid} in + let foo = try + let group = Hashtbl.find groups essid in + group.group_wis <- new_wi::group.group_wis; + with Not_found -> + let group = { group_essid = essid; group_wis = [ new_wi ] } in + Hashtbl.add groups essid group in + new_wi in + let parse_fields fields = + let nodename = head fields in + let rec makepairs l = match l with + [] -> [] + | x::[] -> assert false + | a::b::xs -> (a, b)::(makepairs xs) in + let wis = List.map (parse_pair nodename) (makepairs (tail fields)) in + let sorted_wis = List.sort compare wis in + let node = { node_name = nodename; node_wis = sorted_wis } in + Hashtbl.add nodes nodename node in + List.iter (parse_fields $ (Str.split spacere)) (snarf_lines fname) + ;; + +(* the parsers for the special case components *) + +(** The first field is the nodename, the rest are interface names *) +let parse_nointerference fs = Hashtbl.add nointerference (head fs) (tail fs) +(** Read four fields from the given list and add them as a tuple to the given + list reference *) +let parse_quadruplet l fs = + let f = List.nth fs in + l := (f 0, f 1, f 2, f 3)::!l +(** The first field is the nodename, the rest are channels.*) +let parse_unusable fs = + let channels = List.map int_of_string (tail fs) in + Hashtbl.add unusable (head fs) channels +(** The first field is the supernode name, the rest are the names of the + subnodes. Construct a new node for the supernode and remove the subnodes + from the nodes hash *) +let parse_supernode fs = + let nodename = head fs in + let subnodenames = tail fs in + let subnodes = List.map (Hashtbl.find nodes) subnodenames in + List.iter (Hashtbl.remove nodes) subnodenames; + let prefixed_wis n = List.map (fun w -> { w with wi_name = n.node_name ^ "." ^ w.wi_name}) n.node_wis in + let wis = List.fold_left (fun a s -> a@(prefixed_wis s)) [] subnodes in + let node = { node_name = nodename; node_wis = wis } in + Hashtbl.add nodes nodename node + +let parse_special_conf fname = + let spacere = Str.regexp " " in + let functable = [ ("nointerference", parse_nointerference); + ("important", parse_quadruplet importantlinks); + ("interference", parse_quadruplet interference); + ("unusable", parse_unusable); + ("supernode", parse_supernode) ] in + let do_line fs = (List.assoc (head fs) functable) (tail fs) in + try + List.iter (do_line $ Str.split spacere) (snarf_lines fname) + with x -> () + +(** END PARSING CODE *) + let main = parse_file Sys.argv.(1); - parse_nodeclusters "coupled.conf"; + parse_special_conf "special.conf"; Random.self_init(); let all_nodes = values nodes in Index: nodes/channelga.py =================================================================== --- nodes/channelga.py (revision 1991) +++ (revision ) @@ -1,292 +1,0 @@ -# experiment met evolutionary programming voor de kanalenplanning -# het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld -# fout. wat er wel goed in zit is het parseren van de bestaande situatie en -# het scoren van (nu random) configuraties. -# -# de score functie is nu redelijk simplistisch: -# - de score van een combinatie van twee interfaces op een node is 1 als er -# twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -5 -# als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn -# - de score van een node is de som van de scores van alle combinaties van -# interfaces van die node, maal het aantal interfaces. dat laatste omdat -# een positieve score hebben knapper is met meer interfaces dan met minder, -# dus dat moet beloond. een negatieve score is erger met meer interfaces -# (belangrijker node, waarschijnlijk) dan met minder, dus dat moet -# bestraft. -# - de totale score is de som van de scores van de nodes -# -# het stukje "genetisch" aan het einde is afgeraffeld. mutation en -# recombination gebeuren op de oplossing zelf ipv op een bitstring -# representatie. selection is dom en neemt gewoon de helft beste oplossingen. -# -# lvoge@cs.vu.nl -import re -import random -import os - -# deze twee zijn nodig voor de evaluatie van een configuratie -nodes = {} # nodename -> Node -groups = {} # essid -> WIGroup - -population = [] - -# gegeven een lijst, geef de lijst zonder dubbele elementen -def uniq(l): - d = {} - for e in l: - d[e] = 1 - return d.keys() - -class Node: - def __init__(self, name, wis): - self.name = name - self.wis = wis - self.special = {} - for wi in wis: - wi.setNode(self) - def score(self): - score = 0 - for i in range(len(self.wis)): - wi_i = self.wis[i] - if wi_i.group == None: - # orphaned interface - continue - if wi_i.group.channel == None: - print "huh?" - for j in range(len(self.wis)): - if i != j: - wi_j = self.wis[j] - if wi_j.group == None: - continue - diff = abs(wi_i.group.channel - wi_j.group.channel) - if diff > 2: - score = score + 1 - elif diff == 2: - score = score - 1 - elif diff == 1: - score = score - 5 - else: - score = score - 10 - if self.special.has_key(wi_i.group.channel): - score = score + self.special[wi_i.group.channel] - score = score * len(self.wis) - return score - def setSpecialScoreForChannels(self, score, channels): - for c in channels: - self.special[c] = score - -# een supernode is een verzameling subnodes, bv cetim1, cetim2 en cetim3. -class SuperNode(Node): - def __init__(self, name, nodes): - self.name = name - self.nodes = nodes - self.wis = [] - self.special = {} - for n in nodes: - self.wis.extend(n.wis) - -class WI: - def __init__(self, name): - self.name = name - self.node = None - self.group = None - self.omni = 0 - def setNode(self, node): - self.node = node - def setGroup(self, group): - self.group = group - -class WIGroup: - def __init__(self, name): - self.name = name - self.wis = [] - self.channel = None - def add_wi(self, wi): - self.wis.append(wi) - wi.setGroup(self) - def uniq(self): - self.wis = uniq(self.wis) - -# een configuratie is een bepaalde bedeling van kanalen aan groepen. aangezien -# groepen keyed zijn op essid is de concrete configuratie hier een dict van -# essids naar kanalen. -class Configuration: - def __init__(self): - self.conf = None - self.calculated_score = None - def copy(self): - c = Configuration() - c.conf = self.conf.copy() - c.calculated_score = None - return c - def randomize(self): - self.conf = {} - for essid in groups.keys(): - self.conf[essid] = random.randint(1, 13) - self.calculated_score = None - def score(self): - assert len(self.conf) == len(groups) - if self.calculated_score != None: - return self.calculated_score - for essid in groups.keys(): - groups[essid].channel = self.conf[essid] - score = 0 - for node in nodes.values(): - score = score + node.score() - self.calculated_score = score - return score - def mutate(self, rate): - for essid in groups.keys(): - if random.random() <= rate: - self.conf[essid] = random.randint(1, 13) - def crossover(self, partner, numpoints): - # pick the crossover points - essids = groups.keys() - points = [random.randint(0, len(essids) - 1) for i in range(numpoints)] - points.sort() - conf = {} - who = 0 - lastpoint = 0 - while len(points): - point = points.pop(0) - if who == 0: - d = self.conf - else: - d = partner.conf - who = 1 - who - for i in range(lastpoint, point + 1): - conf[essids[i]] = d[essids[i]] - lastpoint = point - if who == 0: - d = self.conf - else: - d = partner.conf - for i in range(lastpoint, len(essids)): - conf[essids[i]] = d[essids[i]] - assert len(conf) == len(groups) - self.conf = conf - - -# BEGIN UGLY PARSING CODE - -to_resolve = [] # list of (essid, WI) tuples - -def parse_wleiden_conf(lines): - essid = None - wi = None - wis = [] - for l in lines: - if wi != None: - match = re.match("^MODE=master.*", l) - if match != None: - master = 1 - match = re.match("^ESSID=(.*)", l) - if match != None: - essid = match.group(1) - match = re.match("^EW[0-9]*", l) - if match != None: - if master == 1: - group = WIGroup(essid) - groups[essid] = group - group.add_wi(wi) - else: - # defer, may come way later - to_resolve.append( (essid, wi) ) - master = 0 - wi = None - essid = None - else: - match = re.match("^\$nodename='([^']*)';.*", l) - if match != None: - nodename = match.group(1).lower() - match = re.match("^\$config{'wi[0-9]*:[0-9].*", l) - if match != None: - continue - match = re.match("^\$config{'(wi[0-9]*).*", l) - if match != None: - wi = WI(match.group(1)) - wis.append(wi) - master = 0 - node = Node(nodename, wis) - nodes[nodename] = node - -# gegeven een file met filenames van wleiden.conf's, parseer ze allemaal en -# vul de datastructuren -def parse_metafile(filename): - for fname in open(filename).readlines(): - parse_wleiden_conf(open(fname[:-1]).readlines()) - for essid, wi in to_resolve: - if not groups.has_key(essid): - print "Warning: node %s, %s refers to unknown essid %s" % (wi.node.name, wi.name, essid) - continue - groups[essid].add_wi(wi) - for group in groups.values(): - group.uniq() - -def parse_coupled(filename): - try: - for line in open(filename).readlines(): - supername, rest = line[:-1].split(':') - subnodes = [] - for nodename in rest.split(' '): - if nodename == '': - continue - node = nodes[nodename] - del nodes[nodename] - subnodes.append(node) - node = SuperNode(supername, subnodes) - nodes[supername] = node - except: - pass - -def parse_special(filename): - for line in open(filename).readlines(): - fields = line[:-1].split(' ') - nodename = fields[0] - score = int(fields[1]) - channels = map(lambda c: int(c), fields[2:]) - nodes[nodename].setSpecialScoreForChannels(score, channels) - -# END UGLY PARSING CODE - -def plot_configuration(conf, out): - out.write("digraph plot {\n") - for essid in groups: - out.write("\"%s\" [shape=box label=\"%s\\n(%d)\"]\n" % (essid, essid, conf[essid])) - for nodename in nodes.keys(): - for wi in nodes[nodename].wis: - if wi.group == None: - continue - out.write("\"%s\" -> \"%s\"\n" % (nodename, wi.group.name)) - out.write("}") - -parse_metafile('l') -parse_coupled('coupled.conf') -parse_special('special.conf') - -for essid in groups.keys(): - print essid, map(lambda wi: wi.node.name, groups[essid].wis) - -for i in range(20): - conf = Configuration() - conf.randomize() - population.append(conf) - -last_high_score = -10000000 -iterations_since_new_high_score = 0 -while iterations_since_new_high_score < 1000: - for i in range(0, 9): - p = population[i].copy() - #population[i].crossover(population[i + 10], random.randint(1, 4) * 2) - population[i + 10] = p - population[i + 10].mutate(0.05) - population.sort(lambda a, b: cmp(b.score(), a.score())) - high_score = population[0].score() - if high_score > last_high_score: - last_high_score = high_score - iterations_since_new_high_score = 0 - iterations_since_new_high_score = iterations_since_new_high_score + 1 - print high_score -plot_configuration(population[0].conf, open("foo.dot", 'w')) -os.system('neato -Gstart=foo -Goverlap=false/scale -Gsplines=true -Gsep=2 -Gratio=fill -Gnslimit=50.0 -Grotate=90 -Gsize="11,7.5" -Tps -o channelga.ps foo.dot') -