source: proiecte/ptvs/src/vnsim/applications/vitp/routing/RoutingModule.java @ 31

Last change on this file since 31 was 31, checked in by (none), 14 years ago
File size: 18.5 KB
Line 
1/************************************************************************************
2 * Copyright (C) 2008 by Politehnica University of Bucharest and Rutgers University
3 * All rights reserved.
4 * Refer to LICENSE for terms and conditions of use.
5 ***********************************************************************************/
6package vnsim.applications.vitp.routing;
7
8
9
10import java.util.*;
11import java.io.*;
12
13import vnsim.applications.trafficview.SimulatedCarInfo;
14import vnsim.applications.vitp.CarRunningVITP;
15import vnsim.applications.vitp.Statistics;
16import vnsim.applications.vitp.peer.Peer;
17import vnsim.applications.vitp.utils.*;
18import vnsim.core.CarInfo;
19import vnsim.core.Engine;
20import vnsim.map.object.*;
21import vnsim.map.utils.GPSutil;
22import vnsim.vehicular.simulator.CarInstance;
23import vnsim.vehicular.simulator.Location;
24import vnsim.vehicular.simulator.RouteSegment;
25import vnsim.vehicular.simulator.RoutingUtils;
26
27
28
29
30
31
32
33
34public class RoutingModule {
35
36        java.util.Random random=new Random(System.currentTimeMillis());
37
38        MessageIndexModule mim;
39        public CarRunningVITP car;
40        Peer peer;
41
42        public void attachModules(CarRunningVITP car, MessageIndexModule mim, Peer p){
43                this.car=car;
44                this.mim=mim;
45                this.peer=p;
46        }
47
48        public boolean postMessageFromAbove(VITPMessage msg) {
49                //method to be called by the layer above, in order to send a message
50                //to this routing module; returns true, if the message was properly
51                //dealt with, false otherwise
52
53                //the routing module has received a message from the peer; first, it
54                //checks whether it has a valid id; if not, it provides a new one
55
56                if(msg.isIdInval()) {
57                        msg.setMsgId(MessageIndexModule.getNewMessageIdentifier());
58                        mim.addToPending(msg.getId());
59                        //also set the correct source
60                        msg.source=getCurrentRouteSegment();
61                }
62
63                //System.out.println("Has to route a message:"+msg);
64
65                //build a RoutingPacket and route it
66
67                //msg came from above; if it's destination is exactly the current location, then we
68                //are during the computation phase or during the reply delivery phase; in either way,
69                //the routing module should search for the closest neighbor, along the current segmentId
70
71                Location myloc=new Location(car.getRoadIdx(), car.getPointIdx());
72                //check whether destination fits my current location
73
74                //ONLY FOR SOME TESTING PURPOSES! SHOULD NOT BE HERE!!!
75//              if(msg.isRequest()) {
76//                      VITPRequest req=(VITPRequest) msg;
77//                      if(req.isPost()){
78//
79//                              if(!mim.wasBroadcasted(req.getId())) {
80//                                      //broadcast it now and reschedule it
81//                                      //periodically
82//                                     
83////                                    System.out.println("OK : "+car.getVehicleId());
84//                                     
85//                                      mim.addToBroacasted(req.getId());
86//                                      return broadcastPostMessage(req);
87//                              } else {
88////                                    System.out.println("ALREADY : "+car.getVehicleId());
89//                              }
90//                              return true;
91//                      }       
92//              }
93                // END !!!!!!!!!!!!!!!!!!!!!!!!!!!
94
95                if(msg.getDest().contains(myloc)) {
96                        //is it a POST? Then broadcast it
97                        if(msg.isRequest()) {
98                                VITPRequest req=(VITPRequest) msg;
99                                if(req.isPost()){
100                                        if(!mim.wasBroadcasted(req.getId())) {
101                                                //broadcast it now and reschedule it
102                                                //periodically
103                                                mim.addToBroacasted(req.getId());
104                                                return broadcastPostMessage(req);
105                                        } else {
106//                                              System.out.println("ID="+car.getVehicleId()+";WAS BROADCASTED!!!");
107                                        }
108                                        return true;
109                                }       
110                        }
111
112                        //fits
113                        //assume P1 -- C -- N -- P2, where P1,P2=end points of destination route segment,
114                        //C=current location ; N=candidate nodes;
115                        //look among N for the node farthest from P2
116
117                        ArrayList<CarInfo> neighbors=car.trafficDB;
118//                      System.out.println("I am at:"+myloc);
119//                      System.out.println("My neighbors:"+neighbors);
120                        double distance=0;
121                        int indice=-1;
122                       
123                        Integer sentTo=mim.sentTo(msg.getId());
124                       
125                        for(int i=0;i<neighbors.size();i++) {
126                                try {
127                                        if(sentTo!=null) {
128                                                if(neighbors.get(i).getVehicleId()==sentTo)
129                                                        continue;
130                                        }
131                                        Location neig=new Location(neighbors.get(i).getRoadIdx(), neighbors.get(i).getPointIdx());
132                                        if(msg.getDest().checkOrder(myloc, neig)) {
133                                                //neighbor is between C and P2
134//                                              System.out.println("NEIGHBOR IS GOOD:"+neig);
135//                                              System.out.println("DIST BETWEEN:"+msg.getDest().distanceBetween(neig.getLocation()));
136                                                if(msg.getDest().distanceBetween(neig)>distance) {
137                                                        distance=msg.getDest().distanceBetween(neig);
138                                                        indice=i;
139                                                }
140                                        }
141                                } catch (Exception ex) {
142                                        continue; //try another neighbor
143                                }
144                        }
145                        if(distance!=0) {
146                                return unicastPacketToNeighbor( new RoutingPacket(msg, null), neighbors.get(indice) );
147                                //unicast to neighbor 'indice'
148                        } else {
149                                if(msg.isReply()) {
150                                        System.out.println("ROUTING MODULE: No node found during the reply delivery phase! Discarding!");
151                                        return false;
152                                }
153                                try{
154                                        if(((VITPRequest)msg).isPost())
155                                                return true; //a POST message is discarded, as there is no
156                                                                        //other node to send it to.
157                                } catch (ClassCastException ex){
158                                        System.out.println("RoutingModule:ClassCastException:"+ex.toString());
159                                        return false;
160                                }
161                                System.out.println("ROUTING MODULE: No node found during the computation phase; Building the reply!");
162                                //build reply
163                                RoutingPacket packet=buildReply(msg, myloc);
164
165                                try{
166                                        System.out.println("BEFORE!");
167                                        return standardRouting(packet);
168                                } catch(Exception ex){
169                                        System.out.println("RoutingModule.postMessageFromAbove()-EXCEPTION!"+ex.toString());
170                                        return false;
171                                }
172                        }
173                }
174
175                //the destination is not the current segment, so use standard routing, the VITP packet just
176                //came from a peer module, thus the route should be calculated;
177//              ArrayList<RouteSegment> route=RoutingUtils.getUnmergedDijkstraPath(msg.source, msg.dest);
178                ArrayList<RouteSegment> route=RoutingUtils.getUnmergedDijkstraPath(myloc, new Location(msg.dest.roadIndex, msg.dest.pt1));
179
180                route.add(msg.dest);
181
182//              System.out.println("ROUTING MODULE: I have calculated route for packet:"+msg);
183//              System.out.println("THE ROUTE IS: "+route);
184
185                RoutingPacket packet=new RoutingPacket(msg, route);
186                try{
187                        return standardRouting(packet);
188                } catch (Exception ex){
189                        System.out.println("RoutingModule.postMessageFromAbove()-EXCEPTION!"+ex.toString());
190                        return false;
191                }
192        }
193
194        private RoutingPacket buildReply(VITPMessage msg, Location myloc) {
195                VITPReply repret=msg.getReversedVITP();
196                repret.setStatus("ERROR");
197
198                repret.source=new RouteSegment((short)myloc.roadIdx, (short)myloc.ptIdx, (short)myloc.ptIdx);
199
200                System.out.println("ROUTING MODULE: calculating route for packet:"+repret);
201//              ArrayList<RouteSegment> route=RoutingUtils.getUnmergedDijkstraPath(new RouteSegment((short)myloc.roadIdx, (short)myloc.ptIdx, (short)myloc.ptIdx), repret.dest);
202
203                ArrayList<RouteSegment> route=RoutingUtils.getUnmergedDijkstraPath(myloc, new Location(repret.dest.roadIndex, repret.dest.pt1));
204                route.add(repret.dest);
205                System.out.println("DONE CALCULATING ROUTE! ROUTE IS:"+route);
206
207                RoutingPacket packet=new RoutingPacket(repret, route);
208                return packet;
209        }
210
211        public boolean postMessageFromBelow(RoutingPacket packet) {
212                //method to be called by the layer below, in order to send a message
213                //to this routing module; returns true, if the message was properly
214                //dealt with, false otherwise
215
216                //the routing module has received a message from the layer below
217
218                if(peer==null){
219                        System.out.println("ERROR! Routing module not connected with a peer module!");
220                        return false;
221                }
222                VITPMessage msg=packet.msg;
223                Location myloc=new Location(car.getRoadIdx(), car.getPointIdx());
224
225                //System.out.println("ROUTING MODULE; location="+myloc+"; I have received a packet:"+packet);
226
227                if(packet.getNextSegment()!=null) {
228                        if(packet.getNextSegment().contains(myloc))
229                                packet.incrementIndex();
230                }
231               
232                //check if it's a reply for a pending request
233                if(msg.isReply()) {
234                        if(mim.isPending(msg.getId())) {
235                                mim.removeFromPending(msg.getId());
236                                return peer.postMessageFromBelow(msg);
237                        };
238
239                        if(packet.toBroadcast) {
240                                //if I am in the broadcast zone and I did not
241                                //broadcast this message before, then broadcast it
242                                if(!mim.wasBroadcasted(msg.getId())) {
243                                        Point p1=Globals.map.roads.get(myloc.roadIdx).points.get(myloc.ptIdx);
244                                        Point p2=Globals.map.roads.get(packet.roadIndex).points.get(packet.pointIndex);
245                                        double dist=GPSutil.distance(p1, p2);
246                                        if(dist < packet.radius) {
247                                                mim.addToBroacasted(msg.getId());
248                                                return broadcastPacket(packet);
249                                        } else {
250                                                //do not broadcast it further
251//                                              System.out.println("DIST="+dist+"; RADIUS="+packet.radius);
252                                                return true;
253                                        }
254                                }
255                                return true;
256                        }
257
258                        //is it for the current location?
259                        if(msg.getDest().contains(myloc)) {
260                                //it's the first time the message has arrived in
261                                //the destination area; change it to a broadcast
262                                //message
263                                RoutingPacket newPacket=new RoutingPacket(msg, new ArrayList<RouteSegment>());
264                                newPacket.toBroadcast=true;
265                                newPacket.roadIndex=msg.dest.roadIndex;
266                                newPacket.pointIndex=msg.dest.pt2;
267                                newPacket.radius=0.100; //100 meters
268                                mim.addToBroacasted(msg.getId());
269                                return broadcastPacket(newPacket);
270                        }
271
272                                /*
273
274                                OLD METHOD : route the message from vehicle to vehicle
275
276                                //fits
277                                //assume P1 -- C -- N -- P2, where P1,P2=end points of destination route segment,
278                                //C=current location ; N=candidate nodes;
279                                //look among N for the node farthest from P2
280                                ArrayList<SimulatedCarInfo> neighbors=car.neighbors;
281                                double distance=0.0;
282                                int indice=-1;
283                                for(int i=0;i<neighbors.size();i++) {
284                                        Location neig=new Location (neighbors.get(i).getRoadIdx(), neighbors.get(i).getPointIdx());
285
286                                        if(msg.getDest().checkOrder(myloc, neig)) {
287//                                              System.out.println("Dest="+msg.getDest()+";Neighbor:"+neig.getLocation()+" is ok!");
288                                                //neighbor is between C and P2
289                                                if(msg.getDest().distanceBetween(neig)>distance) {
290                                                        distance=msg.getDest().distanceBetween(neig);
291                                                        indice=i;
292                                                }
293                                        }
294                                }
295                                if(indice!=-1) {
296                                        return unicastPacketToNeighbor( new RoutingPacket(msg, null), neighbors.get(indice));
297                                        //unicast to neighbor 'indice'
298                                } else {
299                                        //cannot route this reply! Discard it
300                                        System.out.println("Discarding reply:"+msg);
301                                        return false;
302                                }
303                               
304                                */
305
306                }
307
308                //check if it's a request intended for the local peer
309                if(msg.isRequest()) {
310                        if(msg.getDest().contains(myloc) ) {
311                                return peer.postMessageFromBelow(msg);
312                        } else {
313                                //is it a POST broadcasted from inside its destination area?
314                                //(and it got to me by chance)
315                                //then discard it!
316                                VITPRequest req=(VITPRequest) msg;
317                                if(req.isPost() && packet.toBroadcast)
318                                        return true;
319                        }
320                }
321
322                //if not, then try to route the packet, based on the routing information in it,
323                //find the appropriate neighbor in the neighbors list and
324                //send the packet to it;
325                try{
326                        boolean ret=standardRouting(packet);
327                        if(!ret) {
328                                if(msg.isRequest()) {
329                                        //build reply
330                                        RoutingPacket pack=buildReply(msg, myloc);
331                                        return standardRouting(pack);
332                                } else 
333                                        return false;
334                        }
335                        return true;
336                } catch(Exception ex) {
337                        System.out.println("EXCEPTION-RoutingModule.postMessageFromBelow()");
338                        return false;
339                }
340        }
341
342        public boolean standardRouting(RoutingPacket packet) {
343                //try to find the first node on the next segment (closest to the origin of the next
344                //segment), or the farthest along the same segment (closest to the end of the current
345                //segment); prefer next segment, if there is a node there;
346
347                ArrayList<CarInfo> neighbors=car.trafficDB;
348                Location myloc=new Location(car.getRoadIdx(), car.getPointIdx());
349//              if(myloc==null) {
350//                      System.out.println("ROUTING MODULE: unknown current location - can't route!");
351//                      return false;
352//              }
353
354                if(neighbors==null) {
355                        System.out.println("ROUTING MODULE: No neighbors! Can't route!");
356                        return false;
357                }
358
359                double distance1 = Double.MAX_VALUE;
360                int index1=-1;
361
362                double distance2 = Double.MAX_VALUE;
363                int index2=-1;
364
365//              System.out.println("STANDARD ROUTING! I AM AT:"+car.getVehicleId()+"; POS="+car.getRoadIdx()+";"+car.getPointIdx()+ " SIZE="+car.neighbors.size());
366
367                for(int i=0;i<neighbors.size();i++){
368                       
369                        //CHECK IF THE REAL DISTANCE IS IN FACT LOWER THAN THE WIRELESS RANGE
370                        //THIS CODE IS RELATED TO THE SIMULATION PART, AND SHOULD NOT BE PRESENT HERE
371                        //INSERTED HERE FOR SIMPLICITY
372                       
373                        int id=neighbors.get(i).getVehicleId();
374                        double distance=getRealDistance(car.getVehicleId(), id);
375                        if(distance > Engine.WIRELESS_RANGE) {
376                                continue;
377                        }
378
379                        try {
380                                Location neighbor=new Location(neighbors.get(i).getRoadIdx(), neighbors.get(i).getPointIdx());                         
381//                              System.out.println("CHECKING : "+neighbor);
382                               
383                                if(packet.getNextSegment()!=null && packet.getNextSegment().contains(neighbor)) {
384                                        //that's on the next segment
385//                                      System.out.println("IS ON NEXT SEG!");
386                                        if(packet.getNextSegment().distanceFrom(neighbor) < distance1 ) {
387                                                index1=i;
388//                                              System.out.println("IS BETTER!");
389                                                distance1=packet.getNextSegment().distanceFrom(neighbor);
390                                        }
391                                }
392//                              System.out.println("B--Neighbor:"+i);
393                                if( (packet.getCurrentSegment()!=null && packet.getCurrentSegment().contains(neighbor) && packet.getCurrentSegment().checkOrder(myloc, neighbor)
394                                                || (packet.getCurrentSegment()!=null && !packet.getCurrentSegment().contains(myloc)))) {
395                                        //it's in the same segment; also it's further that myself
396//                                      System.out.println("IS ON SAME SEG!");
397                                        if(packet.getCurrentSegment().distanceBetween(neighbor) < distance2 ) {
398                                                index2=i;
399//                                              System.out.println("IS BETTER!");
400                                                distance2=packet.getCurrentSegment().distanceBetween(neighbor);
401                                        }
402                                }
403                        } catch (Exception ex) {
404                                continue; //try another neighbor
405                        }
406                }
407
408                System.out.flush();
409                if(index1!=-1) {
410                        //there was one node on the next segment
411//                      System.out.println("There was some node on the next segment:"+packet.getNextSegment()+"; ID="+neighbors.get(index1).getVehicleId());
412//                      packet.incrementIndex();
413                        return unicastPacketToNeighbor(packet, neighbors.get(index1));
414                }
415                if(index2!=-1) {
416                        //there was one node on the current segment
417//                      System.out.println("There was nobody on the next segment:"+packet.getNextSegment());
418                        return unicastPacketToNeighbor(packet, neighbors.get(index2));
419                }
420                System.out.println("ROUTING MODULE AT "+car.getRoadIdx()+" ; "+car.getPointIdx()+" : no suitable neighbor found! Discarding packet!");
421                return false;
422        }
423
424        private RouteSegment getCurrentRouteSegment() {
425                //used to set the correct source for a newly generated
426                //VITP request
427
428                int pt1, pt2;
429                int road=car.getRoadIdx();
430                int point=car.getPointIdx();
431                Road r=Globals.map.roads.get(road);
432               
433                if(r.points.size()<point+30) {
434                        pt2=r.points.size()-1;
435                } else {
436                        pt2=point+25;
437                }
438                if(point<25) {
439                        pt1=0;
440                } else {
441                        pt1=point-25;
442                }
443                if(car.getDirection()==0) {
444                        return new RouteSegment((short)road, (short)pt2, (short)pt1);
445                } else {
446                        return new RouteSegment((short)road, (short)pt1, (short)pt2);
447                }
448        }
449
450        private boolean broadcastPostMessage(VITPRequest req) {
451                //probabilistic rebroadcast + delay
452               
453//             
454//              double RAND1=random.nextDouble();
455                double RAND2=random.nextDouble();
456               
457//              if(RAND1*100 > P)
458//                      return true; //probabilistic --> do not broadcast
459               
460                int delay= (int)( RAND2 * 2 * Globals.executionFPS );
461
462                int t=car.scheduleNewSendEvent(Globals.MESSAGE_PROCESSING_TIME+delay, 3000);
463               
464                //System.out.println("BROADCAST; T="+t);
465                car.periodicalBroadcasts.put(t, req.dest);
466               
467                RoutingPacket packet=new RoutingPacket(req, null);
468                packet.toBroadcast=true;
469                ByteArrayOutputStream bos=new ByteArrayOutputStream();
470                try {
471                        ObjectOutputStream oos=new ObjectOutputStream(bos);
472                        oos.writeObject(packet);
473                        oos.flush();
474                        car.messagesToSend.put(t, bos.toByteArray());
475                } catch (Exception ex) {
476                        System.out.println("EXCEPTION RoutingModule UNICAST TO NEIGHBOR:"+ex.toString());
477                        ex.printStackTrace();
478                }
479                return true;
480        }
481
482        private boolean broadcastPacket(RoutingPacket p) {
483
484                Statistics.addBroadcast(p.msg.getId());
485
486//              System.out.println("BROADCASTING "+p);
487                int t=car.scheduleSingleSendEvent(Globals.MESSAGE_PROCESSING_TIME, null);
488                ByteArrayOutputStream bos=new ByteArrayOutputStream();
489                try {
490                        ObjectOutputStream oos=new ObjectOutputStream(bos);
491                        oos.writeObject(p);
492                        oos.flush();
493                        car.messagesToSend.put(t, bos.toByteArray());
494                } catch (Exception ex) {
495                        System.out.println("EXCEPTION RoutingModule UNICAST TO NEIGHBOR:"+ex.toString());
496                        ex.printStackTrace();
497                }
498                return true;
499        }
500
501        private boolean unicastPacketToNeighbor(RoutingPacket p, CarInfo neighbor) {
502
503//              System.out.println("UNICASTING "+p+" TO NEIGHBOR:"+neighbor);
504               
505                Statistics.addHop(p.msg.getId());
506               
507                int delay = (int)(Globals.MESSAGE_PROCESSING_TIME + random.nextDouble()* 2 * Globals.executionFPS);
508                int standardFPSPeriod = (int)((double)(SimulatedCarInfo.STANDARD_MESSAGE_PERIOD * Globals.engine.fps) / 1000);
509                int t = car.scheduleNewSendEvent(delay, new Integer(standardFPSPeriod));
510
511                mim.addToSent(p.msg.getId(),neighbor.getVehicleId());
512
513                ByteArrayOutputStream bos=new ByteArrayOutputStream();
514                try {
515                        ObjectOutputStream oos=new ObjectOutputStream(bos);
516                        oos.writeObject(p);
517                        oos.flush();
518                        car.messagesToSend.put(t, bos.toByteArray());
519                } catch (Exception ex) {
520                        System.out.println("EXCEPTION RoutingModule UNICAST TO NEIGHBOR:"+ex.toString());
521                        ex.printStackTrace();
522                }
523
524                return true;
525        }
526       
527        public static double getRealDistance(int id1, int id2) {
528                //id1, id2 = vehicle ids
529
530                boolean found1=false, found2=false;
531                synchronized(Globals.engine.cars) {
532                        Iterator<SimulatedCarInfo> iter=Globals.engine.cars.iterator();
533                        int rd1=-1, rd2=-1, pt1=-1, pt2=-1;
534                        while(iter.hasNext()) {
535                                SimulatedCarInfo next=iter.next();
536                                if(!found1 && next.getVehicleId()==id1) {
537                                        rd1=next.getRoadIdx();
538                                        pt1=next.getPointIdx();
539                                        found1=true;
540                                }
541                                if(!found2 && next.getVehicleId()==id2) {
542                                        rd2=next.getRoadIdx();
543                                        pt2=next.getPointIdx();
544                                        found2=true;
545                                }
546                        }
547                        if(!found1 || !found2) {
548                                System.out.println("ERROR! RoutingModule.getRealDistance() !");
549                                return Double.MIN_VALUE;
550                        }
551                       
552                        Road r1=Globals.map.roads.get(rd1);
553                        Point p1=r1.points.get(pt1);
554                        Road r2=Globals.map.roads.get(rd2);
555                        Point p2=r2.points.get(pt2);
556                        return GPSutil.distance(p1, p2);
557                }
558        }
559}
Note: See TracBrowser for help on using the repository browser.