/*
* Copyright (c) 2005-2010 KOM – Multimedia Communications Lab
*
* This file is part of PeerfactSim.KOM.
*
* PeerfactSim.KOM is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* any later version.
*
* PeerfactSim.KOM is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with PeerfactSim.KOM. If not, see .
*
*/
package de.tud.kom.p2psim.impl.topology.movement;
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Map;
import java.util.Random;
import java.util.Vector;
import java.util.WeakHashMap;
import javax.swing.JComponent;
import com.google.common.collect.Maps;
import de.tud.kom.p2psim.api.scenario.ConfigurationException;
import de.tud.kom.p2psim.api.topology.movement.SimLocationActuator;
import de.tud.kom.p2psim.api.topology.waypoints.WaypointModel;
import de.tud.kom.p2psim.impl.scenario.simcfg2.annotations.After;
import de.tud.kom.p2psim.impl.scenario.simcfg2.annotations.Configure;
import de.tud.kom.p2psim.impl.topology.util.PositionVector;
import de.tud.kom.p2psim.impl.topology.views.VisualizationTopologyView.VisualizationInjector;
import de.tud.kom.p2psim.impl.topology.views.VisualizationTopologyView.VisualizationInjector.DisplayString;
import de.tud.kom.p2psim.impl.topology.waypoints.graph.StrongWaypoint;
import de.tud.kom.p2psim.impl.topology.waypoints.graph.Waypoint;
import de.tudarmstadt.maki.simonstrator.api.Randoms;
import de.tudarmstadt.maki.simonstrator.api.util.XMLConfigurableConstructor;
/**
* The SLAW Movement Model is based on the implementation in
* BonnMotion Copyright (C) 2002-2010 University of Bonn
* by Zia-Ul-Huda, Gufron Atokhojaev and Florian Schmitt
*
* @author Fabio Zöllner
* @version 1.0, 09.04.2012
*/
public class SLAWMovementModel extends AbstractWaypointMovementModel {
private static final int powerlaw_step = 1;
private static int levy_scale_factor = 1;
private static int powerlaw_mode = 1;
protected Random rand = Randoms
.getRandom(SLAWMovementModel.class);
protected Random xorShiftRandom = new XorShiftRandom(rand.nextLong());
protected double beta = 1;
protected long minpause = 10;
protected long maxpause = 50;
protected double dist_alpha = 3;
protected double cluster_range;
protected int cluster_ratio = 3;
protected int waypoint_ratio = 3;
protected Cluster[] clusters;
protected WeakHashMap movementInformation;
// TODO: minpause and maxpause are currently in microseconds... should be
// changed to minutes
@XMLConfigurableConstructor({"worldX", "worldY", "minpause", "maxpause", "beta", "distAlpha", "clusterRange", "clusterRatio", "waypointRatio" })
public SLAWMovementModel(double worldX, double worldY, long minpause, long maxpause, double beta, double distAlpha, double clusterRange, int clusterRatio, int waypointRatio) {
super(worldX, worldY);
this.minpause = minpause;
this.maxpause = maxpause;
this.dist_alpha = distAlpha;
this.cluster_range = clusterRange;
this.cluster_ratio = clusterRatio;
this.waypoint_ratio = waypointRatio;
movementInformation = new WeakHashMap();
}
@Override
public void nextPosition(SimLocationActuator node) {
// These variables have values same as in the matlab implementation of
// SLAW model by Seongik Hong, NCSU, US (3/10/2009)
if (waypointModel == null) {
throw new ConfigurationException("SLAWMovementModel requires a valid waypoint model which hasn't been provided, cannot execute");
}
SLAWMovementInformation mi = movementInformation.get(node);
if (mi == null) {
//System.err.println("Creating new movement information for node " + node.toString());
mi = new SLAWMovementInformation();
movementInformation.put(node, mi);
}
// log.debug("Selecting new destination for node " + mi.nodeId);
// get random clusters and waypoints
if (mi.clts == null)
mi.clts = make_selection(clusters, null, false);
// get random clusters and waypoints
if (mi.wlist == null)
mi.wlist = get_waypoint_list(mi.clts);
// random source node
if (mi.srcIndex == -1) {
int old = mi.srcIndex;
mi.srcIndex = (int) Math
.floor(randomNextDouble() * mi.wlist.length);
//System.err.println("mi.srcIndex was " + old + " but is now " + mi.srcIndex);
// Set the initial position to the selected waypoint
nextDestination(node, mi.wlist[mi.srcIndex].pos, 0);
//System.err.println("Default case? 0");
return;
}
if (mi.dstIndex != -1) {
mi.srcIndex = mi.dstIndex;
}
int count = 0;
PositionVector source = new PositionVector(node.getRealPosition()
.getX(), node.getRealPosition().getY());
mi.wlist[mi.srcIndex].is_visited = true;
// get list of not visited locations
for (int i = 0; i < mi.wlist.length; i++) {
if (!mi.wlist[i].is_visited) {
count++;
}
}
// if all waypoints are visited then select new clusters and
// waypoints. Destructive mode of original SLAW matlab
// implementation by Seongik Hong, NCSU, US (3/10/2009)
while (count == 0) {
mi.clts = make_selection(clusters, mi.clts, true);
mi.wlist = get_waypoint_list(mi.clts);
for (int i = 0; i < mi.wlist.length; i++) {
if (!mi.wlist[i].is_visited) {
if (source.distanceTo(mi.wlist[i].pos) != 0.0) {
count++;
} else {
mi.wlist[i].is_visited = true;
}
}
}
}
ClusterMember[] not_visited = new ClusterMember[count];
count = 0;
for (int i = 0; i < mi.wlist.length; i++) {
if (!mi.wlist[i].is_visited) {
not_visited[count++] = mi.wlist[i];
}
}
// get distance from source to all remaining waypoints
double[] dist = new double[not_visited.length];
for (int i = 0; i < not_visited.length; i++) {
dist[i] = source.distanceTo(not_visited[i].pos);
}
double[] weights = new double[not_visited.length];
// cumulative sum of distance weights
for (int i = 0; i < weights.length; i++) {
weights[i] = 0;
for (int j = 0; j <= i; j++) {
weights[i] += 1 / Math.pow(dist[j], this.dist_alpha);
}
}
for (int i = 0; i < weights.length; i++) {
weights[i] /= weights[weights.length - 1];
}
double r = randomNextDouble();
int index;
for (index = 0; index < weights.length; index++) {
if (r < weights[index]) {
break;
}
}
// select the next destination
for (int i = 0; i < mi.wlist.length; i++) {
if (mi.wlist[i].pos.equals(not_visited[index].pos)) {
mi.dstIndex = i;
double pauseTime = random_powerlaw(powerlaw_step,
levy_scale_factor, powerlaw_mode)[0];
//System.err.println("Next pause time is " + pauseTime);
nextDestination(
node,
mi.wlist[mi.dstIndex].pos, (long) pauseTime
);
break;
}
}
// change destination to next source
// mi.srcIndex = mi.dstIndex;
}
/**
* returns aggregated list of cluster members from all passed clusters
*
* @param clusters
* clusters list
* @return array of ClusterMember type
*/
protected ClusterMember[] get_waypoint_list(Cluster[] clusters) {
ArrayList result = new ArrayList();
for (Cluster cluster : clusters) {
for (ClusterMember clustermember : cluster.members) {
result.add(clustermember);
}
}
return result.toArray(new ClusterMember[0]);
}
/**
* makes the selection of new clusters and waypoints from passed clusters
*
* @param clusters
* array of clusters to make selection from
* @param change_one
* changes only one of the clusters randomly and then selects new
* waypoints from all clusters
* @return array of selected clusters
*/
protected Cluster[] make_selection(Cluster[] clusters, Cluster[] cur_list,
boolean change_one) {
ArrayList cluster_selection;
if (!change_one) {
// Number of clusters to select
int num_clusters = (int) Math.ceil((double) clusters.length
/ (double) cluster_ratio);
cluster_selection = new ArrayList(num_clusters);
for (int i = 0; i < num_clusters; i++) {
cluster_selection.add(i, -1);
}
int[] total_list = new int[waypointModel.getNumberOfWaypoints(StrongWaypoint.class)];
int counter = 0;
// probability array
for (int i = 0; i < clusters.length; i++) {
for (int j = 0; j < clusters[i].members.length; j++) {
total_list[counter++] = clusters[i].index;
}
}
// select clusters randomly with weights
int t = total_list[(int) Math.floor(this.randomNextDouble()
* waypointModel.getNumberOfWaypoints(StrongWaypoint.class))];
for (int i = 0; i < cluster_selection.size(); i++) {
while (cluster_selection.contains(t)) {
t = total_list[(int) Math.floor(this.randomNextDouble()
* waypointModel.getNumberOfWaypoints(StrongWaypoint.class))];
}
cluster_selection.set(i, t);
}
} else {// just need to change one randomly
cluster_selection = new ArrayList(cur_list.length);
for (Cluster cluster : cur_list) {
cluster_selection.add(cluster.index);
}
}
// change one cluster without weight consideration
cluster_selection = change_one_random(cluster_selection,
clusters.length);
// select waypoints from selected clusters.
Cluster[] result = new Cluster[cluster_selection.size()];
double numberOfWaypoints;
Cluster cluster_iterator = null;
for (int i = 0; i < cluster_selection.size(); i++) {
// find Cluster object in clusters array
for (int j = 0; j < clusters.length; j++) {
if (cluster_selection.get(i) == clusters[j].index) {
cluster_iterator = clusters[j];
break;
}
}
result[i] = new Cluster(cluster_iterator.index);
numberOfWaypoints = (double) cluster_iterator.members.length
/ (double) this.waypoint_ratio;
int[] waypoint_selection;
if (numberOfWaypoints < 1) {
waypoint_selection = select_uniformly(
cluster_iterator.members.length, 1);
} else {
if (this.randomNextDouble() < numberOfWaypoints % 1) {
waypoint_selection = select_uniformly(
cluster_iterator.members.length,
(int) (Math.floor(numberOfWaypoints) + 1));
} else {
waypoint_selection = select_uniformly(
cluster_iterator.members.length,
(int) Math.floor(numberOfWaypoints));
}
}
result[i].members = new ClusterMember[waypoint_selection.length];
for (int j = 0; j < waypoint_selection.length; j++) {
result[i].members[j] = cluster_iterator.members[waypoint_selection[j]]
.clone();
}
}
return result;
}
/**
* changes one of the numbers randomly from the passed array. The new
* changed number is in range [1,n]
*
* @param list
* array of integers
* @param n
* range of numbers
* @return array of integers with one element changed randomly
*/
protected ArrayList change_one_random(ArrayList list,
int n) {
int index = (int) Math.floor(this.randomNextDouble() * list.size());
int value = (int) Math.floor(this.randomNextDouble() * n) + 1;
while (list.contains(value)) {
value = (int) Math.floor(this.randomNextDouble() * n) + 1;
}
list.set(index, value);
return list;
}
/**
* selects k numbers out of n uniformly
*
* @param n
* @param k
* @return array of k integers
*/
protected int[] select_uniformly(int n, int k) {
if (k > n)
throw new RuntimeException(
"SLAW.select_uniformaly(): value of k must not be larger than n.");
int t;
int[] list = new int[k];
for (int i = 0; i < k; i++) {
list[i] = -1;
}
boolean is_in;
int count = 0;
while (count < k) {
is_in = false;
t = (int) Math.floor(this.randomNextDouble() * n);
for (int i = 0; i < list.length; i++) {
if (list[i] == t) {
is_in = true;
break;
}
}
if (!is_in) {
list[count++] = t;
}
}
return list;
}
/**
* Generates random values from power-law distribution.
*
* @param powerlaw_step
* the total numbers to generate. Returns an array of this size.
* @param levy_scale_factor
* levy scaling factor of distribution
* @param powerlaw_mode
* 1: stabrnd 2: reverse computation
* @return double array of powerlaw_step length
**/
protected double[] random_powerlaw(int powerlaw_step,
int levy_scale_factor, int powerlaw_mode) {
double[] result = new double[powerlaw_step];
for (int xi = 0; xi < powerlaw_step;) {
if (powerlaw_mode == 1) { // stabrnd
double[] stabrnd_result = stabrnd(0, levy_scale_factor, 0,
powerlaw_step);
ArrayList temp = new ArrayList();
for (int i = 0; i < stabrnd_result.length; i++) {
if (stabrnd_result[i] > this.minpause
&& stabrnd_result[i] < this.maxpause) {
temp.add(new Double(stabrnd_result[i]));
}
}
if (temp.size() > 0) {
for (Double d : temp) {
result[xi++] = d;
if (xi > powerlaw_step)
break;
}
}
} else if (powerlaw_mode == 2) { // reverse computation
double temp = Math.pow(randomNextDouble(),
1 / (1 - (this.beta + 1))) * this.minpause;
if (temp < this.maxpause) {
result[xi++] = temp;
}
}
}
return result;
}
/**
* Returns array of randomly generated n numbers based on the method of J.M.
* Chambers, C.L. Mallows and B.W. Stuck,
* "A Method for Simulating Stable Random Variables," JASA 71 (1976): 340-4.
*
* @param b
* beta factor
* @param levy_scale_factor
* @param delta
* @param n
* count of random numbers to generate
* @return double array of n length
*/
private double[] stabrnd(double b, int levy_scale_factor, double delta,
int n) {
if (this.beta < .1 || this.beta > 2) {
throw new RuntimeException(
"SLAW.stabrnd(): Beta value must be in [.1,2]");
}
if (Math.abs(b) > 1) {
throw new RuntimeException(
"SLAW.stabrnd(): local beta value must be in [-1,1]");
}
// Generate exponential w and uniform phi
double[] w = new double[n];
double[] x = new double[n];
double[] phi = new double[n];
for (int i = 0; i < n; i++) {
w[i] = -Math.log(randomNextDouble());
phi[i] = (randomNextDouble() - 0.5) * Math.PI;
}
// Gaussian case (Box-Muller)
if (this.beta == 2) {
for (int i = 0; i < n; i++) {
x[i] = 2 * Math.sqrt(w[i]) * Math.sin(phi[i]);
x[i] = delta + levy_scale_factor * x[i];
}
} else if (b == 0) { // Symmetrical cases
if (this.beta == 1) { // Cauchy case
for (int i = 0; i < n; i++) {
x[i] = Math.tan(phi[i]);
}
} else {
for (int i = 0; i < n; i++) {
x[i] = Math.pow(Math.cos((1 - this.beta) * phi[i]) / w[i],
1 / this.beta - 1)
* Math.sin(this.beta * phi[i])
/ Math.pow(Math.cos(phi[i]), 1 / this.beta);
}
}
} else { // General cases
double cosphi, zeta, aphi, a1phi, bphi;
if (Math.abs(this.beta - 1) > 0.00000001) {
for (int i = 0; i < n; i++) {
cosphi = Math.cos(phi[i]);
zeta = b * Math.tan(Math.PI * this.beta / 2);
aphi = this.beta * phi[i];
a1phi = (1 - this.beta) * phi[i];
x[i] = (Math.sin(aphi) + zeta * Math.cos(aphi))
/ cosphi
* Math.pow(
(Math.cos(a1phi) + zeta * Math.sin(a1phi))
/ (w[i] * cosphi), (1 - this.beta)
/ this.beta);
}
} else {
for (int i = 0; i < n; i++) {
cosphi = Math.cos(phi[i]);
bphi = Math.PI / 2 + b * phi[i];
x[i] = 2
/ Math.PI
* (bphi * Math.tan(phi[i]) - b
* Math.log((Math.PI / 2) * w[i] * cosphi
/ bphi));
}
if (this.beta != 1) {
for (int i = 0; i < n; i++) {
x[i] += b * Math.tan(Math.PI * this.beta / 2);
}
}
}
for (int i = 0; i < n; i++) {
x[i] = delta + levy_scale_factor * x[i];
}
}
return x;
}
protected double randomNextDouble(final double value) {
return (randomNextDouble() * value);
}
protected double randomNextDouble() {
return xorShiftRandom.nextDouble();
//return rand.nextDouble();
}
private static final class Cluster {
public ClusterMember[] members;
public int index = -1;
public Cluster(int _index) {
index = _index;
}
public Cluster(int _index, ClusterMember[] _members) {
index = _index;
members = _members;
}
public String toString() {
return "Cluster[index: " + index + "]";
}
}
private static final class ClusterMember {
public int cluster_index = -1;
public PositionVector pos;
public boolean is_visited = false;
public ClusterMember(int _cluster_index, PositionVector _pos,
boolean _is_visited) {
this.cluster_index = _cluster_index;
this.is_visited = _is_visited;
this.pos = _pos;
}
public ClusterMember clone() {
return new ClusterMember(this.cluster_index, this.pos,
this.is_visited);
}
}
private static class SLAWMovementInformation {
public SLAWMovementInformation() {
//
}
public int srcIndex = -1;
public int dstIndex = -1;
public Cluster[] clts = null;
public ClusterMember[] wlist = null;
}
@Configure()
@After(required={WaypointModel.class})
public void _verifyConfig() {
/*
* FIXME: get rid of this method!
*/
Collection strongWaypoints = waypointModel.getWaypoints(StrongWaypoint.class);
if (strongWaypoints == null)
throw new ConfigurationException("The configured waypoint model hasn't generated any strong waypoints that are required by the SLAWMovementModel.");
clusters = generate_clusters(waypointModel);
if (clusters.length <= 2) {
throw new ConfigurationException("The SLAW movement model could only generate 1 cluster, please adjust the cluster range parameter");
}
VisualizationInjector.injectComponent("Clusters", -1, new SLAWClusterOverlay(clusters, waypointModel), false);
VisualizationInjector.addDisplayString(new DisplayString() {
@Override
public String getDisplayString() {
int clusterWps = 0;
for (Cluster c : clusters) {
clusterWps += c.members.length;
}
return "SLAW[Clusters: " + clusters.length + ", WPs in clusters: " + clusterWps + ", Avg per cluster: " + (clusterWps / clusters.length) + "]";
}
});
}
@Override
public void setWaypointModel(WaypointModel waypointModel) {
super.setWaypointModel(waypointModel);
}
/**
* generates clusters
*
* @param waypoints
* list of waypoint s
* @return array of clusters
*/
protected Cluster[] generate_clusters(WaypointModel model) {
Vector all_points = new Vector();
Vector new_points = new Vector();
Vector members = new Vector();
Vector clusters = new Vector();
Vector cluster_members = new Vector();
Waypoint[] waypoints = new Waypoint[]{};
Collection waypointList = model.getWaypoints(StrongWaypoint.class);
if (waypointList == null)
throw new ConfigurationException("The configured waypoint model didn't generate any strong waypoints");
waypoints = waypointList.toArray(waypoints);
for (int i = 0; i < waypoints.length; i++) {
all_points.add(waypoints[i].getPosition());
}
PositionVector init_pos = null;
int cluster_count = 0;
while (!all_points.isEmpty()) {
if (init_pos == null) {
init_pos = all_points.firstElement();
all_points.remove(0);
members.add(init_pos);
}
for (int i = 0; i < all_points.size(); i++) {
PositionVector new_pos = all_points.elementAt(i);
if (init_pos.distanceTo(new_pos) <= this.cluster_range) {
new_points.add(new_pos);
members.add(new_pos);
all_points.remove(i--);
}
}// for all_points
if (!new_points.isEmpty() && !all_points.isEmpty()) {
init_pos = new_points.firstElement();
new_points.remove(0);
}
else {
for (int i = 0; i < members.size(); i++) {
cluster_members.add(new ClusterMember(cluster_count, members.elementAt(i), false));
}
clusters.add(new Cluster(++cluster_count, cluster_members.toArray(new ClusterMember[0])));
cluster_members.clear();
new_points.clear();
members.clear();
init_pos = null;
}
}// while all_points
return clusters.toArray(new Cluster[0]);
}
private class SLAWClusterOverlay extends JComponent {
private Map clusterColors = Maps.newHashMap();
private Cluster[] clusters;
private Random rnd = new Random(System.nanoTime());
private WaypointModel model;
public SLAWClusterOverlay(Cluster[] clusters, WaypointModel model) {
super();
this.clusters = clusters;
this.model = model;
PositionVector dimension = model.getMap().getDimensions();
setBounds(0, 0, (int) dimension.getX(), (int) dimension.getY());
setOpaque(false);
setVisible(true);
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2 = (Graphics2D) g;
g2.setFont(new Font("SansSerif", Font.PLAIN, 9));
for (Cluster c : clusters) {
PositionVector lastPos = null;
Color randomColor = clusterColors.get(c);
if (randomColor == null) {
final float hue = rnd.nextFloat();
// Saturation between 0.1 and 0.3
final float saturation = (rnd.nextInt(2000) + 1000) / 10000f;
final float luminance = 0.9f;
randomColor = Color.getHSBColor(hue, saturation, luminance);
randomColor = new Color(rnd.nextFloat(), rnd.nextFloat(), rnd.nextFloat());
clusterColors.put(c, randomColor);
}
g2.setColor(randomColor);
for (ClusterMember m : c.members) {
if (lastPos == null) lastPos = m.pos;
g2.drawLine((int)lastPos.getX(), (int)lastPos.getY(), (int)m.pos.getX(), (int)m.pos.getY());
lastPos = m.pos;
}
}
}
}
}