dasensor.java

import java.awt.geom.Arc2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Random;


// 普通のセンサクラス
class SensorBase {
    private Point2D.Double position;
    private double         battery;
    private int            s_id; // deprecated
    private int            used_id;
    
    public double          radius;
    public Arc2D.Double    antenna;
    
    final static int UNUSED = -1;
    
    SensorBase(double x, double y, double battery, double radius) {
        position = new Point2D.Double(x, y);
        this.battery = battery;
        this.radius  = radius;
        Arc2D.Double antenna = new Arc2D.Double(x-radius, y-radius,
                                                2*radius, 2*radius, 0, 360.0, Arc2D.PIE);
        this.antenna = antenna;
        used_id = UNUSED;
    }
    
    SensorBase(Point2D.Double p, double battery, double radius) {
        position = p;
        this.battery = battery;
        this.radius  = radius;
        double x = position.x;
        double y = position.y;
        Arc2D.Double antenna = new Arc2D.Double(x-radius, y-radius,
                                                2*radius, 2*radius, 0, 360.0, Arc2D.PIE);
        this.antenna = antenna;
    }
    
    // getter =================================================================
    Point2D.Double getPosition() {
        return position;
    }
    
    double getBattery() {
        return battery;
    }
    
    double getRange() {
        return radius;
    }
    
    // deprecated
    int getSourceId() {
        return s_id;
    }
    
    Arc2D.Double getAntenna() {
        return antenna;
    }
    
    // setter =================================================================
    void setSourceId(int id) {
        s_id = id;
    }
    
    // 受信したときにかかる電力. 単位は[J]
    double receive_energy(int kbyte) {
        double bit_num = kbyte * Math.pow(2, 13); // kbyte ==> bit
        return 50e-9 * bit_num;
    }
    
    // 送信するときにかかる電力. 単位は[J]
    double send_energy(int kbyte) {
        double bit_num = kbyte * Math.pow(2, 13); // kbyte ==> bit
        return receive_energy(kbyte) + 100e-12 * bit_num * Math.pow(this.radius, 2);
    }
    
    // routeの順番にkbyte[KB]のデータを送信する
    // 送信に成功したらtrue, そうでなければfalse
    // routeの先頭には自分自身、次には次に送るノードが格納されている
    boolean send(ArrayList<SensorBase> route, int kbyte) {
        if (!this.equals(route.get(0), 0.01)) {
            System.out.println("error: difference");
            System.out.println("this: " + position);
            System.out.println("route.first: " + route.get(0).getPosition());
            System.exit(1);
        }
        // 受信することもできない
        if(this.battery < receive_energy(kbyte) * 0.417) {
            System.err.println(position + " less battery: " + this.battery);
            return false;
        }
        this.battery -= receive_energy(kbyte) * 0.417; // 1.5V 仮定  1mA = 2.4J
        route.remove(0);
        if (route.isEmpty()) return true;
        
        // 送信することができない
        if(this.battery < send_energy(kbyte) * 0.417) {
            System.err.println(position + " less battery: " + this.battery);
            return false;
        }
        
        this.battery -= send_energy(kbyte) * 0.417;
        return route.get(0).send(route, kbyte);
    }
    
    // fieldの中で半径this.rangeの作る円に入っているSensor全てを返す
    ArrayList<SensorBase> collectSensorsInCircle(ArrayList<SensorBase> field) {
        ArrayList<SensorBase> collection = new ArrayList<SensorBase>();
        
        for(int i = 0; i < field.size(); i++) {
            SensorBase sensor = field.get(i);
            
            if (this.equals(sensor, 0.01)) continue; // 自身は除く
            
            Double distance = this.distance(sensor);
            Double range    = this.radius;
            if(distance.intValue() <= range.intValue()) {
                collection.add(sensor);
            }
        }
        return collection;
    }

    boolean hasCircle() {
        return true;
    }
    
    // 誤差toleranceを認めて、座標が等しいかを確認する
    boolean equals(SensorBase a, double tolerance) {
        double x  = this.position.x;
        double y  = this.position.y;
        double ax = a.getPosition().getX();
        double ay = a.getPosition().getY();
        
        return ax - tolerance <= x && x <= ax + tolerance &&
        ay - tolerance <= y && y <= ay + tolerance;
    }
    
    // aとの距離を返す
    double distance(SensorBase a) {
        return position.distance(a.getPosition());
    }
    
    public String toString() {
        return position.toString();
    }
}

class User extends SensorBase {
    private int user_id;
    private int source_id;
    
    User(Point2D.Double u_p, int u_id, int s_id) {
        super(u_p, 0, 0);
        user_id   = u_id;
        source_id = s_id;
    }
    
    int getUserId() {
        return user_id;
    }
    
    int getSourceId() {
        return source_id;
    }
}

class Source extends SensorBase {
    private int id;
    private boolean is_constraction; // 通信経路を構築しているかどうか
    private ArrayList<ArrayList<SensorBase>> routes; // 構築済みの通信経路の集合
    
    Source(Point2D.Double p, double range, int id) {
        super(p, 0, range);
        this.id = id;
        is_constraction = false;
        routes = new ArrayList<ArrayList<SensorBase>>(30);
        for (int i=0; i < 30; i++) {
            routes.add(new ArrayList<SensorBase>());
        }
    }
    
    boolean send(User u, int kbyte) {
        ArrayList<SensorBase> route = routes.get(u.getUserId());
        if (!this.equals(route.get(0), 0.01)) {
            System.err.println("error: different");
            System.err.println("this: " + this.getPosition());
            System.err.println("route.first: " + route.get(0));
        }
        ArrayList<SensorBase> route_copy = new ArrayList<SensorBase>();
        for (int i = 0; i < route.size(); i++) {
            route_copy.add(route.get(i));
        }
        route_copy.remove(0);
        return route_copy.get(0).send(route_copy, kbyte);
    }
    
    // 疑問: 返す経路にはソースを含むか
    //       含まなくても大丈夫な気がする
    ArrayList<SensorBase> proposal(ArrayList<SensorBase> field, User u) {
        Sensor p, q;
        ArrayList<SensorBase> P, Q, R;
        double E_ave = 10;  // 論文５枚目 バッテリ最大容量の半分
        
        P = new ArrayList<SensorBase>(); // 候補
        Q = new ArrayList<SensorBase>(); // 構築した経路を格納する配列
        R = new ArrayList<SensorBase>(); // 既に使用したノード集合
        
        // step.1
        p = new Sensor(this); // SensorBaseをSensorにキャスト
        Q.add(this);
        q = null; // step.4まで出てこない
        
        while (true) {
            if(is_constraction && (p.getSourceId() != UNUSED)) { // step.2
                for (int i = 0; i < routes.size(); i++) {
                    P.addAll(p.collectSensorsInCircle(routes.get(i)));
                }
                ArrayList<SensorBase> T = new ArrayList<SensorBase>(P); // XXX: 怪しい箇所
                
                // Tから既に使用したノードを除く
                for(int i = 0; i < R.size(); i++) {
                    SensorBase x = R.get(i);
                    if(T.contains(x)) T.remove(x);
                }
                
                double current_angle = p.getAntenna().getAngleStart();
                
                // 左ギリギリまで進む
                while(p.isInSector(T)) {
                    p.rotateDirection(1.0);
                    if(current_angle >= p.getAntenna().getAngleStart() - 0.5 &&
                       current_angle <= p.getAntenna().getAngleStart() + 0.5) {
                        p.getAntenna().setAngleStart(current_angle + 1.0);
                        break;
                    }
                }
                p.rotateDirection(-1.0);
                
                ArrayList<SensorBase> tmp = p.collectSensorsInCircle(field);
                for(int i = 0; i < tmp.size(); i++) {
                    SensorBase sensor = tmp.get(i);
                    double x, y;
                    x = sensor.getPosition().x;
                    y = sensor.getPosition().y;
                    if(p.getAntenna().contains(x, y)) { // 角度γの扇形に含まれる
                        if (!P.contains(sensor)) {
                            P.add(sensor);
                            P.addAll(sensor.collectSensorsInCircle(tmp)); // trick
                        }
                    }
                }
                
                p.getAntenna().setAngleStart(current_angle);
                // 右ギリギリまで進む
                while(p.isInSector(T)) {  // 扇形の中に含まれているかどうか
                    p.rotateDirection(-1.0);
                    if(current_angle >= p.getAntenna().getAngleStart() - 0.5 &&
                       current_angle <= p.getAntenna().getAngleStart() + 0.5) {
                        p.getAntenna().setAngleStart(current_angle - 1.0);
                        break;
                    }
                }
                p.rotateDirection(1.0);
                
                tmp = p.collectSensorsInCircle(field);
                for(int i = 0; i < tmp.size(); i++) {
                    SensorBase sensor = tmp.get(i);
                    double x, y;
                    x = sensor.getPosition().x;
                    y = sensor.getPosition().y;
                    if(p.getAntenna().contains(x, y)) { // 角度γの扇形に含まれる
                        if (!P.contains(sensor)) {
                            P.add(sensor);
                            P.addAll(sensor.collectSensorsInCircle(tmp));
                        }
                    }
                }
            }
            else { // step.3
                ArrayList<SensorBase> tmp = p.collectSensorsInCircle(field);
                for(int i = 0; i < tmp.size(); i++) {
                    SensorBase sensor = tmp.get(i);
                    if(sensor.getBattery() >= E_ave && !R.contains(sensor)) {
                        P.add(sensor);
                    }
                }
                if(P.isEmpty()) {
                    ArrayList<SensorBase> tmp2 = p.collectSensorsInCircle(field);
                    for(int i = 0; i < tmp2.size(); i++) {
                        SensorBase sensor = tmp2.get(i);
                        if(!R.contains(sensor)) {
                            P.add(sensor);
                        }
                    }
                    if(P.isEmpty()) {
                        System.out.println("error");
                        return null; // 失敗
                    }
                }
            }
            
            // step.4
            //(5): 他のソースが構築している通信経路の電波到達範囲内に選択するノードが
            //     含まれていない
            SensorBase jail_break = null;
            double min_distance = 10000000;
            for(int i = 0; i < P.size(); i++) {
                SensorBase sensor = P.get(i);
                if(sensor.getSourceId() == UNUSED || sensor.getSourceId() == id) {
                    if(u.distance(sensor) <= min_distance) {
                        jail_break = sensor;
                        q = new Sensor(sensor); // XXX: 怪しい箇所
                        min_distance = u.distance(sensor);
                    }
                }
            }
            if (q != null) {
                if (p.equals(q)) { // 次の候補が自分自身
                    System.out.println("error: select myself");
                    return null;
                }
                System.out.println("[[[[ADDING SENSOR]]]]; " + q);
                Q.add(jail_break);
                P.clear();
                R.add(jail_break);
                double theta = Math.toDegrees(Math.atan((q.getPosition().y - p.getPosition().y) / (q.getPosition().x - p.getPosition().x) ));
                double dtheta = - theta  - Math.toDegrees(Math.PI / 8);
                p.getAntenna().setAngleStart((dtheta < 0) ? dtheta+360.0 : dtheta);
            }
            else {
                R.add(p);
                p = (Sensor) Q.get(Q.size()-1); // p = last(Q)
                continue; // step.2に戻る
            }
            
            // step.5
            if(q.equals(u, 0.01)) {
                is_constraction = true;
                routes.set(u.getUserId(), Q);
                for (int i = 0; i < Q.size(); i++) {
                    Q.get(i).setSourceId(id);
                }
                return Q;
            }
            R.add(p);
            p = q;
        }
    }
    
    ArrayList<SensorBase> nearest_neighbor(ArrayList<SensorBase> field, User u)
    {
        // 構築された経路
        ArrayList<SensorBase> r = new ArrayList<SensorBase>();
        
        // 次のノードの候補
        ArrayList<SensorBase> R = new ArrayList<SensorBase>();
        
        SensorBase now = this; // 現在のノード
        
        while (!now.equals(u, 0.01))
        {
            // nowの電波到達範囲に入っているノードを集める
            R.clear();
            R.addAll(now.collectSensorsInCircle(field));
            
            Double min  = 1000000.0;
            SensorBase next = null;
            for (int i=0; i < R.size(); i++) {
                SensorBase node = R.get(i);
                Double distance = node.getPosition().distance(u.getPosition());
                if (distance < min) {
                    min  = distance;
                    next = node;
                }
            }
            
            if (next == null) {
                System.err.println("error: can't select");
                return null;
            }
            
            r.add(next);
            now = next;
        }
        routes.set(u.getUserId(), r);
        for(int i = 0; i < r.size(); i++) {
            System.out.println(r.get(i));
        }
        return r;
    }
    
    // 電力考慮版
    ArrayList<SensorBase> nearest_neighbor_improve(ArrayList<SensorBase> field, User u)
    {
        // 構築された経路
        ArrayList<SensorBase> r = new ArrayList<SensorBase>();
        
        // 次のノードの候補
        ArrayList<SensorBase> R = new ArrayList<SensorBase>();
        
        SensorBase now = this; // 現在のノード
        r.add(this);
        
        while (!now.equals(u, 0.01))
        {
            // nowの電波到達範囲に入っているノードを集める
            R.clear();
            R.addAll(now.collectSensorsInCircle(field));
            
            Double min  = 1000000.0;
            SensorBase next = null;
            for (int i=0; i < R.size(); i++) {
                SensorBase node = R.get(i);
                if (node.getBattery() < 10) continue;
                Double distance = node.getPosition().distance(u.getPosition());
                if (distance < min) {
                    min  = distance;
                    next = node;
                }
            }
            
            if (next == null) {
                System.err.println("error: can't select");
                return null;
            }
            
            if (r.contains(next)) {
                System.err.println("error: select twice");
                return null;
            }
            
            r.add(next);
            now = next;
        }
        routes.set(u.getUserId(), r);
        for(int i = 0; i < r.size(); i++) {
            System.out.println(r.get(i));
        }
        return r;
    }
    
}

// 指向性アンテナを持つセンサクラス
class Sensor extends SensorBase {
    private int  used_id; // 自分を通信経路に使っているソースのID
    
    Sensor(Point2D.Double p, double battery, double range, Arc2D.Double arc) {
        super(p, battery, range);
        antenna  = arc;
        used_id  = UNUSED;
    }
    
    Sensor(SensorBase a) {
        super(a.getPosition(), a.getBattery(), a.getRange());
    }
    
    int getSourceId() {
        return used_id;
    }
    
    Arc2D.Double getAntenna() {
        return antenna;
    }
    
    void setSourceId(int id) {
        used_id = id;
    }
    
    
    // アンテナの始点の角度をdegree度変更する
    void rotateDirection(double degree) {
        double angle = antenna.getAngleStart();
        double diff = angle + degree;
        if (diff >= 360.0)
            diff -= 360;
        else if (diff < 0)
            diff += 360;
        antenna.setAngleStart(diff);
    }
    
    // Sensor集合のSensor全てが扇型の中に入っているかどうか
    boolean isInSector(ArrayList<SensorBase> s) {
        for(int i = 0; i < s.size(); i++) {
            double x = s.get(i).getPosition().x;
            double y = s.get(i).getPosition().y;
            if(!antenna.contains(x, y)) {
                return false;
            }
        }
        return true;
    }

    boolean hasCircle() {
        return false;
    }
}


public class DASensor {
    final static double a = 28.290; // 論文５枚目 格子点の間隔
    final static int width  = 11; // 横のセンサの個数
    final static int height = 18; // 縦のセンサの個数
    final static double angle = 45.0;
    final static double max_battery = 2000; // [mA]
    final static double range = Math.sqrt(2)*a; // [m]
    
    final static Random rnd = new Random(2014L);
    
    static ArrayList<SensorBase> field;
    static ArrayList<Source> sources;
    
    static void MakeField() {
        field = new ArrayList<SensorBase>(width * height);
        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                Point2D.Double p = new Point2D.Double(a*j,a*i);
                Arc2D.Double arc = new Arc2D.Double(a*j - range, a*i - range, 2*range,
                                                    2*range, angle, angle, Arc2D.PIE);
                field.add(new Sensor(p, max_battery, range, arc));
            }
        }
    }
    
    static void MakeSource() {
        sources = new ArrayList<Source>();
        sources.add(new Source(new Point2D.Double(88, 0), 40, 0)); // 座標はテキトー
    }
    
    static boolean IsUseUser(int num) {
        int ran = rnd.nextInt(10000);
        if(ran < num)
            return true;
        else
            return false;
    }
    
    public static void main(String[] args) {
        // ユーザのx, y座標
        double[] users_coord = {
            282.90, 480.93,
            226.32, 282.90,
            28.29, 367.77,
            56.58, 198.03,
            0, 169.74,
            113.16, 282.90,
            169.74, 169.74,
            141.45, 367.77,
            84.87, 113.16,
            0,  28.29,
            226.32,  84.87,
            56.58, 311.19,
            84.87, 226.32,
            226.32, 169.74,
            198.03, 311.19,
            84.87, 396.06,
            0, 480.93,
            56.58, 452.64,
            169.74, 452.64,
            226.32, 367.77,
        };
        
        // ユーザの作成
        User[] users = new User[30];
        for (int i=0; i < 20; i++) {
            users[i] = new User(new Point2D.Double(users_coord[2*i], users_coord[2*i+1]), i, 0);
        }
        
        MakeField();
        MakeSource();
        
        /*
         int end_time = 100;
         for (int time=0; time < end_time; time++) {
         ArrayList<SensorBase> result = new ArrayList<SensorBase>();
         result = sources.get(0).proposal(field, users[0]);
         System.out.print("send message...");
         if (sources.get(0).send(result, 10)) // resultの順に10KByteのデータを送信
         System.out.println("success");
         else
         System.out.println("fail");
         }
         */
        
        int[] check = new int[20];
        for(int i = 0; i < 20; i++) {
            check[i] = -1;
        }
        
        int fail_count = 0;
        int try_count  = 0;
        int null_count = 0;
        
        int end_time_sec = 60 * 60 * 12;
        for(int time_sec = 1; time_sec <= end_time_sec; time_sec++) {
            for(int i = 0; i < 20; i++) {
                if(check[i] < 0) {
                    if(IsUseUser(7)) {
                        System.out.println("constraction user "+ users[i].getUserId());
                        try_count++;
                        if (sources.get(0).nearest_neighbor_improve(field, users[i]) == null) {
                            System.err.println("error: route cann't constract");
                            null_count++;
                            continue;
                        }
                        check[i] = 60;
                        System.out.println(time_sec + "sec spent");
                    }
                }
                else {
                    check[i]--;
                }
                
                if (check[i] >= 0) {
                    if(!sources.get(0).send(users[i], 220)) {
                        System.out.println(users[i].getUserId() + "user send fail");
                        check[i] = -1;
                        fail_count++;
                    }
                }
            }
            // System.out.println(time_sec + "sec spent");
        }
        System.out.println("fail count: " + fail_count);
        double sum_battery = .0;
        for (int i=0; i < field.size(); i++) {
            sum_battery += field.get(i).getBattery();
            System.err.println("battery: " + field.get(i).getBattery());
        }
        System.out.println("battery ratio(%): " + sum_battery / (max_battery * field.size()) * 100);
        System.out.println("error ratio(%)  : " + fail_count * 100.0 / try_count + " ( " + fail_count + ", " + try_count + " )");
        System.out.println("cant contst ratio(%)  : " + null_count * 100.0 / try_count + " ( " + null_count + ", " + try_count + " )");
    }
}