Luận văn Đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng manet

ls/cmu-scene-gen/setdest của bộ mô phỏng NS2. Phương pháp thứ hai thực thi sự di chuyển ngẫu nhiên của nút như sau: $mobilenode start Với phương pháp này ban đầu nút di động có vị trí ngẫu nhiên và sau đó có các cập nhật để thay đổi hướng và tốc độ của nút. Các giá trị đích đến và tốc độ được tạo theo cách ngẫu nhiên. Các di chuyển của nút di động được thực thi trong C++. Bất luận việc sử dụng phương pháp nào để tạo ra sự di chuyển cho nút thì hình trạng của các nút di động cần phải được định nghĩa. Nó nên được định nghĩa trước khi tạo ra các nút di động. Thông thường hình trạng phẳng được tạo ra bằng cách xác định độ dài và rộng của hình trạng mạng như sau: set topo [new Topography] $topo load_flatgrid $opt(x) $opt(y) Trong đó $opt(x) và $opt(y) là các biên trong mô phỏng. 4.3.2. Quá trình mô phỏng mạng MANET với NS2 [1] Quá trình mô phỏng mạng MANET với bộ mô phỏng NS2 thông thường trải qua các bước như sau trong việc xây dựng tệp kịch bản: 4.3.2.1. Tạo bộ lập lịch các sự kiện + Tạo bộ lập lịch set ns [new Simulator] + Lập lịch sự kiện $ns at + Khởi động bộ lập lịch $ns run 4.3.2.2. Ghi lại vết các sự kiện của mạng mô phỏng + Dò vết các gói tin trên tất cả các liên kết, xuất ra tệp test.out $ns trace-all [open test.out w] + Dò vết các gói tin trên tất cả các liên kết, xuất ra định dạng nam 53 $ns namtrace-all [open test.nam w] + Cũng có thể chỉ “dò vết” một số tham số, thí dụ: $ns trace-queue $n0 $n1 $ns namtrace-queue $n0 $n1 4.3.2.3. Thiết lập mạng mô phỏng + Thiết lập topo mạng set topo [new Topography] $topo load_flatgrid $val(x) $val(y) set god_ [create-god $val(nn)] 4.3.2.4. Cấu hình nút di động + Cấu hình nút di động $ns_ node-config -adhocRouting $val(rp) \ -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 \ -movementTrace OFF + Khởi tạo vị trí ban đầu cho các nút $node_(0) set X_ 5.0 $node_(0) set Y_ 2.0 $node_(0) set Z_ 0.0 $node_(1) set X_ 390.0 $node_(1) set Y_ 385.0 $node_(1) set Z_ 0.0 + Thiết lập sự di chuyển cho nút di động $ns_ at 50.0 "$node_(1) setdest 25.0 20.0 15.0” 4.3.2.5. Tạo ra các nguồn sinh lưu lượng + Tạo lưu lượng set tcp [new Agent/TCP] $tcp set class_ 2 set sink [new Agent/TCPSink] $ns_ attach-agent $node_(0) $tcp $ns_ attach-agent $node_(1) $sink 54 $ns_ connect $tcp $sink set ftp [new Application/FTP] $ftp attach-agent $tcp $ns_ at 10.0 "$ftp start" + Việc tạo lưu lượng có thể lấy từ tệp sinh lưu lượng của công cụ có sẵn trong bộ mô phỏng NS2 4.3.2.6. Xác định thời điểm dừng for {set i 0} {$i < $val(nn) } {incr i} { $ns_ at 150.0 "$node_($i) reset"; } $ns_ at 150.0001 "stop" $ns_ at 150.0002 "puts \"NS EXITING...\" ; $ns_ halt" proc stop {} { global ns_ tracefd nf $ns_ flush-trace close $tracefd close $nf } Việc xác định thời gian dừng (hay thời gian mô phỏng cần thiết) là quan trọng bởi vì nếu như có kéo dài thời gian mô phỏng thêm thì độ chính xác của kết quả cũng không tăng thêm mà chi phí phải trả lại tăng tỉ lệ thuận với thời gian mô phỏng. Lý do là bởi quá trình mô phỏng sinh ra các tệp vết chiếm nhiều dung lượng ổ đĩa cứng. Người ta khuyến cáo rằng với mô phỏng mạng MANET thời gian mô phỏng thường khoảng vài trăm giây trở nên. 4.3.3. Tích hợp giao thức TORA và OLSR vào bộ mô phỏng NS2 Bản thân bộ mô phỏng NS2, phiên bản 2.34 đã hỗ trợ các giao thức định tuyến MANET sau: AODV, DSDV, DSR và TORA. Tuy nhiên trong bốn giao thức trên thì với giao thức định tuyến TORA, phần mềm NS2 khi chạy trong môi trường Linux, ở một số phiên bản (như version 2.34 được cài trên máy của tôi), thường gặp một số lỗi trong các tệp tora.h và tora.cc và khi gặp lời gọi hàm của lệnh command tora. Qua tìm kiếm các ý kiến trao đổi trên các diễn đàn trên Internet về NS2, tôi đã thử sửa đổi các tệp theo nhiều cách để khắc phục lỗi trên. Đến khi đọc tài liệu [21], tôi đã sửa được lỗi này bằng cách thay đổi các tệp này theo cách sau: + Với tệp tora.h: Ta thêm các dòng sau trong phần khai báo biến protected protected: /* for passing packets up to agents */ PortClassifier *dmux_; }; + Với tệp tora.cc: Ta thêm đoạn mã sau vào lệnh else cuối cùng của định nghĩa hàm toraAgent::command 55 else if (strcmp(argv[1], "port-dmux") == 0) { dmux_ = (PortClassifier *)TclObject::lookup(argv[2]); if (dmux_ == 0) { fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__, argv[1], argv[2]); return TCL_ERROR; } return TCL_OK; } Sau đó chúng ta tiến hành biên dịch lại chương trình NS2 (trên máy của tôi là bộ Ns-allinone phiên bản 2.34), cụ thể bằng các thao tác sau đây: ü Đầu tiên cần kiểm tra các gói phần mềm cần thiết cho việc biên dịch lại NS2 đã được cài đặt sẵn hay chưa, ví dụ như: gcc, glib-header, zlib... Để cài đặt gói gcc chẳng hạn, chạy lệnh như sau (trên Ubuntu 9.04 và có kết nối mạng Internet): sudo apt-get install gcc ü Tiếp theo vào thư mục gốc của bộ mô phỏng ns-2.34 chạy lệnh như sau sudo ./install ü Trong quá trình cài đặt nếu có thông báo lỗi thiếu gói dữ liệu nào thì có thể cài thêm tương tự như cài đặt ở trên hoặc có thể tham khảo một số lỗi tại ü Nếu không có vấn đề gì thì khoảng 10-15 phút (trên máy của tôi) quá trình biên dịch lại bộ mô phỏng NS2 sẽ hoàn thành. ü Để kiểm tra việc cài đặt có thành công không, chúng ta có thể sử dụng công cụ validate như sau trong thư mục ns-2.34: sudo ./validate Tuy nhiên, một lỗi nghiêm trọng khác xảy ra khi chạy mô phỏng với giao thức TORA là chương trình dường như rơi vào chu kỳ chết và không có phản hồi nào cho kết quả mô phỏng. Qua quá trình tìm hiểu trên Internet, tôi phát hiện ra vấn đề nằm ở tệp imep/imep.cc trong bộ mô phỏng NS2 [19]. Tiến hành sửa đổi tệp này bằng cách ở dòng 504 ta thay dòng lệnh rexmitTimer.start(rexat - CURRENT_TIME); bằng đoạn mã if (rexat-CURRENT_TIME<0.000001) // Preventing eternal loop. rexmitTimer.start(0.000001); else rexmitTimer.start(rexat - CURRENT_TIME); Sau đó tiến hành biên dịch lại bộ mô phỏng NS2, theo cách tương tự như mô tả ở trên. Với việc sửa đổi như vậy, tôi đã chạy được giao thức TORA với số nút tham gia là 3 và thời gian mô phỏng ngắn khoảng 100s. Với số nút và thời gian mô phỏng 56 lớn hơn, việc rơi vào chu kỳ chết lại xảy ra. Do thời gian thực hiện luận văn cao học có thời hạn, mà việc sửa đổi để giao thức TORA chạy đúng cần rất nhiều thời gian, nên tôi quyết định để lại việc mô phỏng với giao thức định tuyến TORA cho các nghiên cứu sau. Tôi tin rằng mình có thể làm được hoặc trong cộng đồng nghiên cứu cũng đã có người giải quyết được vấn đề này. Với giao thức định tuyến OLSR, để tích hợp vào bộ mô phỏng NS2 chúng ta cần tải mã nguồn tại sau đó copy tệp um-olsr- 0.8.8.tgz vào thư mục ns-allinone-2.34/ns-2.34 và chạy các câu lệnh như sau: $ cd ns-allinone-2.34/ns-2.34/ $ tar -zxvf um-olsr-0.8.8.tgz $ ln -s ./um-olsr-0.8.8 ./olsr $ patch -p1 < olsr/um-olsr-2.34_v0.8.8.patch Tệp sửa lỗi patch tải tại 2.34_v0.8.8.patch. Tiến hành biên dịch lại bộ mô phỏng NS2 để tích hợp giao thức OLSR vào bộ mô phỏng NS2. Quá trình biên dịch lại NS2 theo cách tương tự như đã trình bày ở mục trên. 4.4. Đánh giá bằng mô phỏng chi phí tìm đường một số giao thức định tuyến chủ yếu trong mạng MANET Trong mục này tôi sẽ trình bày việc đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET dựa trên công cụ mô phỏng NS2 với các giao thức điển hình là AODV, DSDV, DSR và OLSR trong các ngữ cảnh khác nhau. Để tiếp cận một cách có hệ thống bài toán đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET trước tiên ta phải xác định được các tham số của môi trường (hệ thống) trong quá trình mô phỏng, các độ đo hiệu năng được chọn làm tiêu chuẩn so sánh. Sau đó tôi sẽ thực hiện một dãy các thí nghiệm với các ngữ cảnh khác nhau nhằm đưa ra được lượng thông tin lớn nhất về chi phí tìm đường với nỗ lực nhỏ nhất. Cuối cùng là việc phân tích và đánh giá các kết quả thu được từ quá trình mô phỏng dưới dạng biểu đồ để từ đó đưa ra các kết luận, nhận xét. 4.4.1. Các độ đo hiệu năng được đánh giá [1] Với một hệ thống mạng thì các độ đo hiệu năng có thể chia thành hai loại chính đó là các độ đo hướng tới người sử dụng như thời gian đáp ứng, thời gian phản ứng của hệ thống và các độ đo hướng tới hệ thống như thông lượng, thời gian trễ, hệ số sử dụng đường truyền. Để đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET tôi sử dụng các độ đo sau: ü Số gói tin định tuyến trung bình cần phát theo từng giây: Là số các gói tin định tuyến cần phát từ nút cần gửi dữ liệu cộng với số lần các gói tin này được chuyển tiếp (forward) bởi các nút trung gian chia cho thời gian mô phỏng để có thể tìm được đường tới nút đích. 57 ü Chi phí định tuyến chuẩn hóa theo tải: Chi phí định tuyến chuẩn hóa theo tải ở đây tôi sử dụng để đánh giá chi phí tìm đường là tỉ lệ giữa tổng số gói tin định tuyến cần phát (cả gửi và chuyển tiếp) so với tổng số gói tin định tuyến cần phát (cả gửi và chuyển tiếp) cộng với tổng số gói tin dữ liệu được gửi và chuyển tiếp. Chi phí định tuyến chuẩn hóa theo tải được chuẩn hóa về 1. ü Thời gian phát hiện tuyến trung bình: Thời gian phát hiện tuyến trung bình được định nghĩa là thời gian trung bình từ lúc nút nguồn bắt đầu gửi gói tin Route Request cho tới thời điểm bắt đầu gửi gói tin dữ liệu đầu tiên. Thời gian phát hiện tuyến trung bình được đánh giá và so sánh với hai giao thức định tuyến khởi tạo phía nguồn là AODV và DSR. 4.4.2. Thiết lập các lựa chọn, tham số mô phỏng [17] Như đã trình bày ở trên, do đặc thù của mạng MANET là mạng động với băng thông thấp, năng lượng của nút hạn chế cho nên khi nghiên cứu về chi phí tìm đường của các giao thức định tuyến mạng MANET ta cần chú ý đến một số lựa chọn, tham số mô phỏng như: ü Kích thước mạng (độ lớn của mạng): Số lượng nút trong mạng ü Mật độ nút: Tính theo số hàng xóm trung bình hoặc theo số nút trung bình trong diện tích phủ sóng (radio range) của một nút. ü Độ linh động của mạng: Được đo bằng tốc độ chuyển động trung bình của các nút mạng. ü Tỉ lệ các liên kết đơn hướng: Khi hệ thống vận hành với sự tồn tại của các liên kết đơn hướng thì ảnh hưởng như thế nào ü Các mẫu lưu lượng: Hệ thống với các mẫu lưu lượng như CBR hoặc TCP chẳng hạn. 4.4.3. Các ngữ cảnh mô phỏng Ngữ cảnh mô phỏng mạng MANET được cấu thành bởi các yếu tố như tô-pô mạng, mô hình chuyển động, mô hình sinh lưu lượng, diện tích và hình dạng vùng mô phỏng, thời gian hoạt động của các nguồn sinh lưu lượng, thời gian mô phỏng. Bằng cách thay đổi các yếu tố kể trên sẽ cho chúng ta những ngữ cảnh mạng khác nhau. Trong luận văn cao học này, kịch bản mô phỏng tôi xây dựng gồm 50 nút có vị trí khởi tạo ngẫu nhiên trong một vùng địa lý có kích thước 1500x300m với phạm vi truyền sóng vô tuyến của mỗi nút là 250m (bán kính). Tọa độ của mỗi nút tại một vị trí trong vùng mô phỏng có dạng (x,y,z) trong đó z có giá trị bằng 0. Nút di chuyển theo hai mô hình di chuyển là Random Waypoint và Random Walk. Theo mô hình Random Waypoint, đầu tiên nút có một vị trí ngẫu nhiên trong khu vực mô phỏng và ở tại đó một khoảng thời gian gọi là thời gian tạm dừng. Khi quãng thời gian này hết hạn, nút chọn ngẫu nhiên một đích trong khu vực mô phỏng và một tốc độ được phân bố đồng đều giữa [Speedmin, Speedmax]. Sau đó, nút di chuyển tới vị trí mới với tốc độ đã chọn. Khi tới vị trí mới, nút dừng một khoảng thời gian được chọn theo phân bố đồng đều 58 giữa [Pmin, Pmax] và sau đó tiếp tục lại quá trình. Mô hình Random Walk mô phỏng chuyển động ngẫu nhiên của các thực thể trong tự nhiên. Nút di động di chuyển từ vị trí hiện tại tới vị trí mới bằng việc chọn ngẫu nhiên hướng nằm trong khoảng [0,180o], tốc độ nằm trong khoảng [Speedmin, Speedmax]. Mỗi chuyển động diễn ra trong khoảng thời gian travel_time hoặc khoảng cách hằng số, không có khoảng thời gian tạm dừng trước khi nút thay đổi hướng và tốc độ. Các thí nghiệm tôi tiến hành có thời gian mô phỏng là 15 phút (tương ứng với 900s). Thực thể truyền thông CBR được gắn trên nút có tốc độ phát gói tin không đổi là 4 gói tin/giây và các gói tin có kích thước 512 byte. Số lượng nguồn phát CBR cho mỗi mô hình di chuyển là 1, 3 và 5 nguồn phát. Để đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET, trong mô hình Random Waypoint tôi tiến hành mô phỏng với 7 mẫu thời gian tạm dừng (0, 150, 300, 450, 600, 750 và 900s). Tiến hành mô phỏng với mô hình Random Walk, tôi sử dụng thời gian di chuyển (travel time) là 10s. Như vậy tổng số thí nghiệm mô phỏng mạng MANET tôi thực hiện sẽ là 96 thí nghiệm bao gồm: ü Mô hình Random Waypoint: 7 mẫu thời gian tạm dừng x 3 mẫu nguồn phát CBR x 4 mẫu giao thức định tuyến mạng MANET = 84 thí nghiệm. ü Mô hình Random Walk: 1 mẫu thời gian di chuyển x 3 mẫu nguồn phát CBR x 4 mẫu giao thức định tuyến mạng MANET = 12 thí nghiệm. Trong mỗi thí nghiệm mô phỏng, các tham số mô phỏng giống nhau được cho bởi bảng 5: Tham số mô phỏng Giá trị Phạm vi truyền sóng vô tuyến của nút di động 250m Băng thông 2Mbps Số nút tham gia mô phỏng 50 Vùng mô phỏng 1500x300m Thời gian mô phỏng 900s Tốc độ di chuyển cực tiểu 0m/s Dạng truyền thông CBR Số nguồn phát 1, 3, 5 Tốc độ gửi gói tin 4 gói tin/ giây Kích thước gói tin 512 bytes Bảng 5. Các đặc điểm ngữ cảnh giống nhau của thí nghiệm mô phỏng Các giao thức định tuyến mạng MANET như AODV, DSDV, DSR và OLSR phải được thực hiện trong cùng điều kiện tải và giống nhau về các tham số mô phỏng để đảm bảo việc so sánh, đánh giá giữa các giao thức là chuẩn xác. Do đó, với tệp tạo ngữ cảnh (lvch-dcthanh.tcl) với mỗi giao thức sẽ có các tham số và tải giống nhau, chỉ khác nhau ở phương thức định tuyến được sử dụng, thời gian tạm dừng/thời gian di chuyển và số nguồn phát CBR. Sau khi chạy xong các kịch bản ngữ cảnh thì bộ mô phỏng sẽ sinh ra các tệp vết ghi lại các sự kiện xảy ra trong quá trình mô phỏng. Tôi sẽ 59 dùng các đoạn mã bằng ngôn ngữ perl do tôi tự viết để tính toán, đánh giá cho các độ đo hiệu năng mong muốn. Để tạo các tệp di chuyển theo mô hình Random WayPoint cho nút di động tôi dùng công cụ setdest trong thư mục ~ns/indep-utils/cmu-scen-gen/setdest nằm trong bộ mô phỏng NS2. Chạy setdest với các tham số sau để tạo hình trạng mạng với các thời gian tạm dừng khác nhau: ./setdest –v -n -p -s -t -x -y > / ./setdest –v 1 –n 50 –p 0 –s 20 -t 900 –x 1440 –y 900 > rwp_0 ./setdest –v 1 –n 50 –p 150 –s 20 -t 900 –x 1500 –y 300 > rwp_150 ./setdest –v 1 –n 50 –p 300 –s 20 -t 900 –x 1500 –y 300 > rwp_300 ./setdest –v 1 –n 50 –p 450 –s 20 -t 900 –x 1500 –y 300 > rwp_450 ./setdest –v 1 –n 50 –p 600 –s 20 -t 900 –x 1500 –y 300 > rwp_600 ./setdest –v 1 –n 50 –p 750 –s 20 -t 900 –x 1500 –y 300 > rwp_750 ./setdest –v 1 –n 50 –p 900 –s 20 -t 900 –x 1500 –y 300 > rwp_900 Để tạo các tệp di chuyển nút di động với mô hình Random Walk tôi dùng công cụ rwalk được mô tả chi tiết tại [18]. Tiến hành tải mã của chương trình tại rồi giải nén ra ta sẽ thấy ba thư mục là palm-general, palm-graph và palm-rw. Tiếp đến ta chuyển vào thư mục palm-rw rồi tiến hành gõ lệnh make, chương trình rwalk sẽ được cài đặt. Để tạo tệp di chuyển chạy dòng lệnh như sau: ./rwalk 3 50 1500 300 900 10 0 0 0 10 0 > rwalk Để tạo các tệp mẫu lưu lượng CBR, tôi sử dụng bộ tạo lưu lượng nằm trong thư mục ~ns/indep-utils/cmu-scene-gen của bộ mô phỏng NS2 có tên là cbrgen.tcl với số nguồn phát khác nhau : ns cbrgen.tcl [-type cbr|tcp] [-nn nodes] [-seed seed] [-mc connections] [-rate rate] ns cbrgen.tcl –type cbr –nn 50 –seed 1.0 –mc 1 –rate 4.0 > cbr_1 ns cbrgen.tcl –type cbr –nn 50 –seed 1.0 –mc 3 –rate 4.0 > cbr_3 ns cbrgen.tcl –type cbr –nn 50 –seed 1.0 –mc 5 –rate 4.0 > cbr_5 Sau khi xây dựng kịch bản mô phỏng bằng ngôn ngữ tcl (tệp lvch-dcthanh.tcl), tôi tiến hành thực hiện mô phỏng từ dòng lệnh. Cú pháp cho kịch bản mô phỏng như sau: 60 ns lvch-dcthanh.tcl [-nn nodes] [-x MAXX] [-y MAXY] [-rp Routing protocol] [-cp conn pattern] [-sc scenario] [-stop sec] [-ifq interface queue] [-nout namout] [-tout traceout] Trong đó: -nn : Số nút tham gia mô phỏng (mặc định là 50) -x : Bề rộng của vùng mô phỏng (mặc định là 1500m) -y : Bề dài của vùng mô phỏng (mặc định là 300m) -rp : Giao thức định tuyến mạng MANET sử dụng trong mô phỏng (mặc định là DSDV) -cp : Tệp mẫu lưu lượng đưa vào (mặc định là tệp ‘connection_pattern’) -sc : Tệp ngữ cảnh của mô phỏng (mặc định là tệp ‘scenario_file’) -stop : Thời gian kết thúc mô phỏng (mặc định là 900s) -ifq : Kiểu giao diện hàng đợi (mặc định là kiểu Queue/DropTail/PriQueue) -nout, -tout : Là các tệp vết ghi lại các sự kiện xảy ra trong mô phỏng 4.4.3.1. Ngữ cảnh 1 (Mô hình Random Waypoint) [19] Với ngữ cảnh 1, tôi sử dụng mô hình di chuyển Random Waypoint được tạo bởi công cụ setdest nằm trong bộ mô phỏng NS2. Kịch bản mô phỏng tôi xây dựng gồm các đặc điểm ngữ cảnh chung được mô tả ở mục trên. Các đặc điểm ngữ cảnh riêng bao gồm tốc độ di chuyển cực đại của nút di động là 20m/s. Các giá trị thời gian tạm dừng tôi chọn lần lượt là 0, 150, 300, 450, 600, 750 và 900s. Thời gian tạm dừng bằng 0s ứng với việc các nút di chuyển liên tục trong suốt thời gian mô phỏng, còn thời gian tạm dừng bằng 900s tương ứng với các nút đứng yên trong suốt thời gian mô phỏng. Như vậy ta có bảng 6 tổng kết các tham số mô phỏng với mô hình Random Waypoint bao gồm tốc độ di chuyển cực đại và các khoảng thời gian tạm dừng (các tham số khác được cho bởi bảng 5): Tham số mô phỏng Giá trị Tốc độ di chuyển cực đại 20m/s Thời gian tạm dừng 0, 150, 300, 450, 600, 750, 900 s Bảng 6. Hình trạng mô phỏng với mô hình Random Waypoint Các dòng lệnh mô phỏng áp dụng cho mô hình di chuyển Random Waypoint lần lượt với các giao thức định tuyến mạng MANET và các thời gian tạm dừng mô phỏng khác nhau và số nguồn phát CBR khác nhau. Trong các dòng lệnh dưới đây giá trị [i] lần lượt là thời gian tạm dừng của mô hình di chuyển Random Waypoint ứng với 0, 150, 300, 450, 600, 750 và 900. Giá trị [j] lần lượt là số nguồn phát CBR ứng với 1, 3 và 5. Giao thức DSDV ns lvch-dcthanh.tcl –sc rwp_[i] –cp cbr_[j] –nout dsdv[j]_[i].nam –tout dsdv[j]_[i].tr Giao thức AODV 61 ns lvch-dcthanh.tcl –rp AODV –sc rwp_[i] –cp cbr_[j] – nout aodv[j]_[i].nam –tout aodv[j]_[i].tr Giao thức DSR ns lvch-dcthanh.tcl –rp DSR –ifq CMUPriQueue –sc rwp_[i] –cp cbr_[j] –nout dsr[j]_[i].nam –tout dsr[j]_[i].tr Giao thức OLSR ns lvch-dcthanh.tcl –rp OLSR –sc rwp_[i] –cp cbr_[j] – nout olsr[j]_[i].nam –tout olsr[j]_[i].tr Các sự kiện xảy ra trong mô phỏng với việc chạy với 4 giao thức định tuyến AODV, DSDV, DSR và OLSR được xuất ra các tệp vết như trên. Hình ảnh mạng mô phỏng với 50 nút mạng có thể thấy như sau (tại thời điểm t = 24.746015s như trên hình): Hình 18. Hình ảnh 50 nút di động, giao thức DSDV, thời gian tạm dừng 0, 1 nguồn phát * Phân tích tệp vết để tính các tham số hiệu năng Sau khi thu được các tệp vết tôi sử dụng các kịch bản viết bằng ngôn ngữ perl (xem phụ lục 2,3,4 và 5) chạy với tệp vết để thu được các kết quả về chi phí tìm đường của 4 giao thức định tuyến mạng MANET. Các kết quả được so sánh dưới đây bao gồm: Số gói tin định tuyến trung bình cần phát theo từng giây, chi phí định tuyến chuẩn hóa theo tải và thời gian phát hiện tuyến trung bình. Hình 19 thể hiện số gói tin định tuyến trung bình cần phát theo từng giây của 4 giao thức định tuyến AODV, DSDV, DSR và OLSR trong trường hợp sử dụng 1, 3 và 5 nguồn phát CBR. Có thể nhận thấy rằng khi số nguồn phát CBR tăng thì số lượng gói tin định tuyến trung bình cần phát cũng tăng. Điều này cũng dễ hiểu bởi khi có càng nhiều nguồn phát thì thông tin định tuyến trao đổi trong mạng mô phỏng càng nhiều để bảo đảm nút nguồn có thể tìm được đường đi tới nút đích. Ngoài ra chúng ta cũng có thể thấy khi thời gian tạm dừng tăng lên từ 0 đến 900s thì số lượng gói tin định tuyến trung bình cần phát cũng giảm bởi các nút từ chỗ di chuyển liên tục đến tạm dừng hầu như không di chuyển làm cho các cập nhật thông tin định tuyến ít dần 62 đi. Nhờ đó việc trao đổi thông tin định tuyến giảm đi bởi sự thay đổi vị trí của nút là thưa dần. Khi thời gian tạm dừng tăng đến 900s (nút không di chuyển), với 2 giao thức định tuyến AODV và DSR, 2 đường tiệm cận trục hoành; còn với 2 giao thức định tuyến DSDV và OLSR, 2 đường đi xuống nhưng không sát trục hoành. Nguyên nhân là hai giao thức định tuyến bảng DSDV và OLSR đều duy trì bảng định tuyến của mình bằng cách truyền các gói tin cập nhật định tuyến thường xuyên để bảo đảm tuyến đường lúc nào cũng có sẵn, do đó 2 đường không thể tiệm cận trục hoành. Hình 19d có vài điểm bất thường, có thể giải thích rằng đây là những điểm bùng phát do lỗi hoặc do cấu hình di chuyển ban đầu gây tắc nghẽn mạng nghiêm trọng làm cho số gói tin định tuyến trung bình cần phát tăng lên một cách đột ngột. Hình 20 hiển thị chi tiết về số gói tin định tuyến trung bình cần phát khi so sánh giữa 4 giao thức định tuyến mạng MANET với cùng số nguồn phát CBR lần lượt là 1, 3 và 5. Trong cả ba trường hợp với số nguồn phát khác nhau, ta thấy số lượng gói tin định tuyến trung bình cần phát sử dụng bởi giao thức định tuyến DSR là ít nhất. Kế cận ngay đó là giao thức định tuyến AODV. Số gói tin định tuyến trung bình cần phát nhiều hơn DSR và AODV xảy ra đối với giao thức định tuyến DSDV. Giao thức định tuyến bảng OLSR sử dụng số gói tin định tuyến trung bình cần phát nhiều nhất để phát hiện đường đi từ nút nguồn đến nút đích. Điều này có thể giải thích là do hai giao thức định tuyến AODV và DSR là hai giao thức định tuyến khởi tạo phía nguồn, nó chỉ gửi truy vấn tìm đường mỗi khi có yêu cầu. Hai giao thức định tuyến bảng DSDV và OLSR đều duy trì bảng định tuyến của mình bằng cách truyền các gói tin cập nhật định tuyến thường xuyên để bảo đảm tuyến đường lúc nào cũng có sẵn. Việc duy trì tuyến đường được thực hiện nhờ các quảng bá định tuyến làm cho số lượng gói tin định tuyến trung bình cần phát cao hơn so với hai giao thức định tuyến khởi tạo phía nguồn. Ngoài ra OLSR là giao thức định tuyến đa đường chứa nhiều đường đi từ nút nguồn đến nút đích còn DSDV chỉ có một tuyến đường từ nút nguồn đến nút đích, nên OLSR tốn nhiều gói tin cập nhật tuyến hơn so với DSDV. 63 Hình 19. Số gói tin định tuyến trung bình cần phát với 1, 3 và 5 nguồn phát (a) DSDV (b) AODV (c) DSR (d) OLSR 64 Hình 20. Số gói tin định tuyến trung bình cần phát với 4 giao thức định tuyến MANET (a) 1 nguồn phát (b) 3 nguồn phát (c) 5 nguồn phát 65 Một độ đo đánh giá chi phí tìm đường khác được đưa ra so sánh giữa các giao thức định tuyến mạng MANET là chi phí định tuyến chuẩn hóa theo tải. Hình 21 là thể hiện chi phí định tuyến chuẩn hóa theo tải với các trường hợp 1, 3 và 5 nguồn phát của 4 giao thức định tuyến mạng MANET. Có thể thấy rằng khi số nguồn phát CBR tăng lên thì chi phí định tuyến chuẩn hóa theo tải giảm dần. Ngoài ra khi mà thời gian tạm dừng tăng lên thì chi phí định tuyến chuẩn hóa theo tải cũng giảm dần. Chi phí định tuyến chuẩn hóa theo tải cao nhất trong trường hợp sử dụng giao thức định tuyến OLSR với thời gian tạm dừng là 0s và thấp nhất trong trường hợp sử dụng giao thức định tuyến nguồn AODV và DSR với thời gian tạm dừng là 900s. So sánh giữa các giao thức định tuyến mạng MANET với cùng số nguồn phát về chi phí định tuyến chuẩn hóa theo tải được minh họa trong hình 22, ta thấy trong cả ba trường hợp sử dụng 1, 3 và 5 nguồn phát, chi phí định tuyến chuẩn hóa theo tải của DSR và AODV đều thấp hơn so với DSDV và OLSR. Trong cùng số nguồn phát CBR, với mỗi giao thức định tuyến MANET, có thể thấy rằng khi thời gian tạm dừng tăng lên thì chi phí định tuyến chuẩn hóa theo tải giảm dần. Nguyên nhân có thể giải thích như sau, nếu coi A là tổng số gói tin định tuyến, B là tổng số gói tin dữ liệu thì chi phí định tuyến chuẩn hóa theo tải cho bởi công thức BA A Cost + = Biến đổi công thức trên như sau: BA B BA BBA BA A Cost + -= + -+ = + = 1 Như biện luận ở mục trên, khi thời gian tạm dừng tăng lên thì tổng số gói tin định tuyến giảm dần (A giảm), nguồn CBR phát dữ liệu không đổi (B không đổi). Do đó ta có: A+B ¯ => • + BA B => ¯ + - BA B 1 Ngoài ra giao thức định tuyến OLSR chiếm chi phí định tuyến chuẩn hóa theo tải cao nhất. Giao thức DSDV chịu chi phí định tuyến chuẩn hóa theo tải thấp hơn so với OLSR. 66 Hình 21. Chi phí định tuyến chuẩn hóa theo tải với 1, 3 và 5 nguồn phát (a) DSDV (b) AODV (c) DSR (d) OLSR 67 Hình 22. Chi phí định tuyến chuẩn hóa theo tải với 4 giao thức định tuyến MANET (b) 3 nguồn phát (c) 5 nguồn phát 68 Chi phí tìm đường cuối cùng tôi sử dụng để so sánh giữa các giao thức định tuyến mạng MANET là thời gian phát hiện tuyến trung bình. Độ đo này tôi tiến hành đánh giá giữa hai giao thức định tuyến khởi tạo phía nguồn là AODV và DSR. Hình 23 mô tả thời gian phát hiện tuyến trung bình với số nguồn phát là 1, 3 và 5 của hai giao thức định tuyến AODV và DSR. Từ hình vẽ ta thấy khi mà số nguồn phát CBR tăng thì thời gian phát hiện tuyến trung bình cũng tăng lên. Điều này có thể giải thích là do có nhiều nguồn cùng phát nên để tìm được đường từ nút nguồn đến lúc đích thì phải tốn thời gian hơn. Ngoài ra khi thời gian tạm dừng tăng lên thì thời gian phát hiện tuyến cũng tăng theo. Hình 24 minh họa thời gian phát hiện tuyến trung bình của AODV và DSR với cùng số nguồn phát CBR. Từ hình vẽ có thể thấy thời gian phát hiện tuyến trung bình đối với giao thức định tuyến AODV nhiều hơn so với giao thức định tuyến DSR. Nguyên nhân có thể giải thích là giao thức định tuyến DSR lưu trữ nhiều tuyến đường từ nút nguồn tới nút đích. Khi xảy ra lỗi liên kết, DSR có thể sử dụng các tuyến còn lại mà không cần mất thời gian cho việc phát hiện lại tuyến do đó giảm được thời gian phát hiện tuyến trung bình. Tuy nhiên sự chênh lệch về thời gian phát hiện tuyến trung bình giữa AODV và DSR không phải là quá cách xa nhau. 69 Hình 23. Thời gian phát hiện tuyến trung bình với 1, 3 và 5 nguồn phát (b) AODV (c) DSR 70 Hình 24. Thời gian phát hiện tuyến trung bình với 2 giao thức định tuyến MANET (a) 1 nguồn phát (b) 3 nguồn phát (c) 5 nguồn phát 71 4.4.3.2. Ngữ cảnh 2 (Mô hình Random Walk) Với ngữ cảnh 2, ta sử dụng mô hình di chuyển Random Walk. Tương tự mô hình Random Waypoint các đặc điểm ngữ cảnh chung cũng được sử dụng trong thí nghiệm mô phỏng của tôi. Với mô hình Random Walk tôi sử dụng tốc độ di chuyển cực đại của nút di động là 10m/s. Quãng thời gian di chuyển (travel time) tôi chọn là 10s để đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET. Như vậy ta có bảng 7 tổng kết các tham số mô phỏng với mô hình Random Walk bao gồm tốc độ di chuyển cực đại và thời gian di chuyển (các tham số khác được cho bởi bảng 5): Bảng 7. Hình trạng mô phỏng với mô hình Random Walk Sau khi tạo ra đầy đủ các tệp ngữ cảnh và mẫu lưu lượng, ta tiến hành chạy tệp kịch bản lvch-dcthanh.tcl với cú pháp như sau cho 4 giao thức định tuyến mạng MANET Giao thức DSDV ns lvch-dcthanh.tcl –sc rwalk –cp cbr_[j] –nout dsdv_rwalk_[j].nam –tout dsdv_rwalk_[j].tr Giao thức AODV ns lvch-dcthanh.tcl –rp AODV –sc rwalk –cp cbr_[j] –nout aodv_rwalk_[j].nam –tout aodv_rwalk_[j].tr Giao thức DSR ns lvch-dcthanh.tcl –rp DSR –ifq CMUPriQueue –sc rwalk – cp cbr_[j] –nout dsr_rwalk_[j].nam –tout dsr_rwalk_[j].tr Giao thức OLSR ns lvch-dcthanh.tcl –rp OLSR –sc rwalk –cp cbr_[j] –nout olsr_rwalk_[j].nam –tout olsr_rwalk_[j].tr trong đó j là số nguồn phát: 1, 3 và 5. * Phân tích tệp vết để tính các tham số hiệu năng Sau khi thu được các tệp vết ta sử dụng các kịch bản viết bằng ngôn ngữ perl chạy với tệp vết để thu được các kết quả về chi phí tìm đường với mô hình Random Walk của 4 giao thức định tuyến mạng MANET. Hình 25 cho thấy với mô hình di chuyển Random Walk thì số gói tin định tuyến trung bình cần phát của OLSR vẫn luôn cao hơn so với các giao thức định tuyến còn lại. Hai giao thức định tuyến AODV và DSR có số gói tin định tuyến trung bình cần phát gần như nhau và thấp hơn so với giao thức định tuyến DSDV. Ngoài ra khi số nguồn phát CBR tăng thì số gói tin định tuyến trung bình cần phát cũng tăng lên. Tham số mô phỏng Giá trị Tốc độ di chuyển cực đại 10m/s Thời gian di chuyển 10s 72 Hình 25. Số gói tin định tuyến trung bình cần phát trong mô hình Random Walk Chi phí định tuyến chuẩn hóa theo tải thì lại giảm dần khi mà số nguồn phát CBR tăng lên và OLSR vẫn chiếm chi phí định tuyến chuẩn hóa theo tải cao nhất (gần bằng 1 với trường hợp sử dụng 1 nguồn phát CBR). Hình 26. Chi phí định tuyến chuẩn hóa theo tải trong mô hình Random Walk Thời gian phát hiện tuyến trung bình trong mô hình Random Walk cũng tăng khi mà số lượng nguồn phát CBR tăng. Ngoài ra có thể thấy giao thức định tuyến AODV tốn thời gian tìm đường hơn so với giao thức định tuyến nguồn khác là DSR. 73 Hình 27. Thời gian phát hiện tuyến trung bình trong mô hình Random Walk 4.4.4. Đánh giá, nhận xét chi phí tìm đường của một số giao thức định tuyến mạng MANET Với mục đích đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng MANET, tôi đã xây dựng thí nghiệm mô phỏng với hai mô hình di chuyển là Random Waypoint và Random Walk, tiến hành đánh giá, so sánh giữa bốn giao thức định tuyến mạng MANET bao gồm AODV, DSDV, DSR và OLSR. Thông qua quá trình mô phỏng, mỗi giao thức định tuyến thể hiện chi phí tìm đường khác nhau. Sau đây là những kết luận chung về chi phí tìm đường của từng giao thức định tuyến và giữa các giao thức định tuyến với nhau. DSDV là giao thức định tuyến dựa trên bảng cung cấp một đường đi tới một đích bất kỳ. Giao thức định tuyến này hoạt động hiệu quả khi số nguồn sinh lưu lượng đưa vào mạng thấp và mức độ di chuyển của các nút mạng là ít. Khi số nguồn sinh lưu lượng đưa vào mạng hoặc mức độ di chuyển của các nút di động tăng thì việc cập nhật định tuyến diễn ra với tần suất lớn. Cụ thể trong thí nghiệm mô phỏng, khi tôi tăng thời gian tạm dừng từ 0s đến 900s và giảm số nguồn sinh lưu lượng đưa vào mạng từ 5 về 1 nguồn thì số gói tin định tuyến trung bình cần phát giảm đi đáng kể. Cũng là giao thức định tuyến dựa trên bảng, OLSR có số lượng gói tin định tuyến trung bình cần phát và chi phí định tuyến chuẩn hóa theo tải cao hơn nhiều so với các giao thức định tuyến AODV và DSR. Điều này cũng dễ hiểu vì OLSR phải thực hiện nhiệm vụ định tuyến trước. Giao thức này hoạt động hiệu quả khi có tập lớn các nút truyền thông với nhau và các cặp [nguồn, đích] thay đổi nhanh theo thời gian nhờ sử dụng một tập các chuyển phát đa điểm MRP. Một cách chi tiết, khi tôi tăng số nguồn sinh lưu lượng đưa vào mạng từ 1 tới 3, rồi từ 3 tới 5, số gói tin định tuyến trung bình cần phát giữa ba mức không chênh lệch nhau quá nhiều, cụ thể với thời gian tạm dừng bằng 150s thì các giá trị số gói tin định tuyến trung bình cần phát lần 74 lượt là 61.42, 61.64 và 61.73. Từ đó có thể cho thấy khi mà số nguồn sinh lưu lượng đưa vào càng nhiều thì giao thức hoạt động càng trở lên hiệu quả. Với hai giao thức định tuyến bảng DSDV và OLSR, số lượng gói tin định tuyến trung bình cần phát và chi phí định tuyến chuẩn hóa theo tải tuy là cao hơn so với AODV và DSR nhưng bù lại chúng không cần phải mất thời gian để phát hiện các tuyến từ nút nguồn tới nút đích bởi tuyến đường tới đích đã có sẵn trong bảng định tuyến của chúng. Nhờ đó mà không phải tốn bất kỳ chi phí về thời gian nào cho việc phát hiện tuyến nữa. Hai giao thức đạt kết quả khá tốt về chi phí tìm đường có thể thấy rõ là AODV và DSR về khả năng tiết kiệm số gói tin định tuyến trung bình cần phát và chi phí định tuyến chuẩn hóa theo tải. Là hai giao thức có yêu cầu khởi tạo phía nguồn nên khi có yêu cầu truyền dữ liệu từ nút nguồn tới nút đích chúng mới thi hành việc kiểm tra có tồn tại tuyến hay không do đó để tìm được đường đi từ nút nguồn tới nút đích chúng phải chịu một độ trễ thời gian nhất định cho việc phát hiện tuyến. Cụ thể trong các trường hợp tôi tiến hành thí nghiệm về thời gian tạm dừng và số nguồn sinh lưu lượng thay đổi, số gói tin định tuyến trung bình cần phát và chi phí định tuyến chuẩn hóa theo tải của hai giao thức yêu cầu khởi tạo phía nguồn đều thấp hơn rõ rệt so với hai giao thức định tuyến dựa trên bảng, Khi thời gian tạm dừng lên tới 900s (các nút không di chuyển) thì hai độ đo này đều có xu hướng tiến về 0. Giao thức AODV hoạt động hiệu quả khi có các liên kết đối xứng giữa các nút di động và có thời gian phát hiện tuyến thấp khi các nút di chuyển liên tục. Cụ thể trong thí nghiệm mô phỏng của tôi, khi thời gian tạm dừng là 0 (các nút di chuyển trong suốt quá trình mô phỏng) với số nguồn sinh lưu lượng tăng từ 1 tới 5 thì thời gian phát hiện tuyến trung bình chỉ dao động từ 0.035 tới 0.046s. Giao thức định tuyến nguồn còn lại là DSR có thời gian phát hiện tuyến trung bình tốt hơn so với giao thức định tuyến AODV. Điều này được giải thích bởi DSR có nhiều tuyến tới đích hơn, khi việc lỗi tuyến hay mất tuyến xảy ra, nó có thể sử dụng một trong những tuyến còn lại thay vì khởi tạo một quá trình tìm tuyến mới. Giao thức DSR hoạt động đặc biệt hiệu quả trong trường hợp các nút di động di chuyển với mức độ trung bình. Cụ thể, trong thí nghiệm mô phỏng của tôi, với thời gian tạm dừng dao động từ 300-600s, thời gian phát hiện tuyến tăng rất chậm và thay đổi không đáng kể. Khi mà thời gian tạm dừng quá thấp hoặc quá cao thì thời gian phát hiện tuyến không đạt kết quả tối ưu, cụ thể khi thời gian tạm dừng là 900s, sự biến đổi thời gian phát hiện tuyến tăng vọt lên, trong trường hợp với số nguồn phát là 3 thì thời gian phát hiện tuyến tốn gần 0.07s. 75 KẾT LUẬN Đề tài luận văn ‘Đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng MANET’ đề cập đến vấn đề đi tìm chi phí tìm đường của một số giao thức định tuyến điển hình trong mạng MANET, một vấn đề quan trọng trong lĩnh vực mạng không dây. Sau quá trình nghiên cứu, luận văn đã đạt được một số kết quả nhất định cả về lý thuyết và thực nghiệm. Luận văn đã trình bày tổng quan về khái niệm và các đặc điểm của mạng WLAN và mạng MANET. Ngoài ra, luận văn cũng xem xét bài toán định tuyến trong mạng MANET và các giải pháp có thể sử dụng để giải quyết bài toán định tuyến cũng như giới thiệu một số giao thức định tuyến điển hình trong mạng MANET. Đi cùng với lý thuyết là phần thực nghiệm mô phỏng, tôi đã tích hợp một số giao thức định tuyến mạng MANET vào bộ chương trình mô phỏng NS2 như OLSR, TORA. Quá trình tích hợp các giao thức này được trình bày chi tiết trong luận văn. Sau đó, luận văn cũng mô tả việc xây dựng 96 thí nghiệm mô phỏng từ 4 giao thức định tuyến mạng MANET là AODV, DSDV, DSR và OLSR và việc thay đổi các ngữ cảnh mạng bao gồm việc thay đổi số nguồn sinh lưu lượng (1, 3, 5 nguồn), thay đổi mô hình chuyển động (mô hình Random Waypoint, mô hình Random Walk). Bằng việc sử dụng các tệp mã được tôi viết bằng ngôn ngữ perl, tôi đã đưa ra được các đồ thị so sánh về chi phí tìm đường của một số giao thức định tuyến mạng MANET khảo sát và từ đó đánh giá các độ đo chi phí tìm đường bao gồm số gói tin định tuyến trung bình cần phát, chi phí định tuyến chuẩn hóa theo tải và thời gian phát hiện tuyến trung bình. Mặc dù vậy, do điều kiện và thời gian hạn chế nên luận văn không tránh khỏi những thiếu sót. Trong tương lai gần, tôi sẽ tiếp tục đánh giá chi phí tìm đường với một số giao thức định tuyến khác như TORA, ZRP… bằng cách tích hợp thêm các giao thức mới vào bộ chương trình mô phỏng NS2 theo hai hướng là tìm kiếm các mô đun sửa lỗi cho các giao thức định tuyến mạng MANET cần tích hợp hoặc trực tiếp phát triển các thư viện để có thể tích hợp vào bộ chương trình mô phỏng NS2. Sau bước đó, tôi sẽ tiến hành các thí nghiệm mô phỏng, viết thêm các tệp kịch bản phân tích các kết quả để đưa ra được các nhận xét sâu sắc và chính xác hơn về sự hiệu quả của các giao thức định tuyến mạng MANET trong những điều kiện mạng cụ thể. Ngoài ra, còn có một số vấn đề khác liên quan đến mạng MANET khá thú vị và cần nghiên cứu, khảo sát như: ü Vấn đề bảo mật trong mạng MANET ü Vấn đề bảo đảm chất lượng dịch vụ trong mạng MANET ü Vấn đề đánh giá dung lượng của mạng MANET… 76 TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt 1. PGS.TS. Nguyễn Đình Việt, Bài giảng đánh giá hiệu năng mạng máy tính, 2008. Tài liệu Tiếng Anh 2. Chai-Kong Toh, A Novel Distributed Routing Protocol To Support AdHoc Mobile Computing, Proc IEEE 15th, Mar. 1996. 3. Charles E. Perkins, Elizabeth M.Royer, Ad-hoc On-Demand Distance Vector Routing, Proc 2nd IEEE Wksp. Mobile Comps. Sys and App, Feb 1999. 4. Charles E. Perkins, Pravin Bhagwat, Highly Dynamic Destination-Sequenced Distance Vector Routing (DSDV) for Mobile Computers, Comp Commun Rev, Oct. 1994. 5. Ching-Chuan Chiang, Hsiao-Kuang Wu, Winston Liu, Mario Gerla, Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel, PROC IEEE SICON 97, Apr. 1997. 6. David B. Johnson, David A. Maltz, Josh Broch, DSR: The Dynamic Source Routing Protocol for Multi-hop Wireless Ad Hoc Networks, t. Imielinski and H.Korth , Eds Kluwer, 1996. 7. Eitan Altman, Tania Jimenez, NS Simulator for beginners, Lecture notes, 2003- 2004. 8. Elizabeth M.Royer, Chai-Keong Toh, A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks, IEEE Personal Communications, Apr. 1999. 9. Kevin Fall, Kannan Varadhan, The NS Manual, The VINT Project, A Collaboration between researchers at UC Berkeley, LBL, USC/ISI, and Xerox PARC, May. 2010. 10. Mr. Ankur Khetrapal, Routing techniques for Mobile Ad Hoc Networks Classification and Qualitative/Quantitative Analysis, Internet Conference on Wireless Networks, 2006. 11. M. S. Corson, A. Ephremides, A Distributed Routing Algorithm for Mobile Wireless Networks, Feb. 1995. 12. Mathew Gast, 802.11 Wireless Networks: The Definitive Guide, O’Reilly Publisher, 2002. 13. Rohit Dube, Cynthia D. Rais, Kuang-Yeh Wang, Satish K. Tripathi, Signal Stability-Based Adaptive Routing (SSA) for Adhoc Mobile Networks, IEEE Pers. Commun, Feb. 1997. 14. Shree Murthy, J.J. Garia-Luna-Aceves, An Efficient Routing Protocol for Wireless Networks, ACM Mobile Networks and Apps, Oct. 1996. 77 15. Stefano Basagni, Marco Conti, Silvia Giordano, Ivan Stojmenovic, Mobile ad hoc networking, John Wiley & Sons, Inc., Publication, 2004. 16. T.Clausen, P.Jacquet, P.Muhlethaler, A.Laouiti, A.Qayyum, L.Viennot, Optimized Link State Routing Protocol for Adhoc Networks, Multi Topic Conference, 2001. 17. 18. 19. 04/ 20. 21. 22. 78 PHỤ LỤC 1. lvch-dcthanh.tcl # Written by Doan Cao Thanh (15/08/2010) # Mobile nodes : 50 # Area : 1500x300m # Time : 900s # Default Script Options set opt(chan) Channel/WirelessChannel ;# Channel type set opt(prop) Propagation/TwoRayGround ;# Radio propagation model set opt(netif) Phy/WirelessPhy ;# Network interface type set opt(mac) Mac/802_11 ;# Mac type set opt(ifq) Queue/DropTail/PriQueue ;# Interace queue type set opt(ll) LL ;# Link layer type set opt(ant) Antenna/OmniAntenna ;# Antenna model set opt(x) 1500 ;# X dimension set opt(y) 300 ;# Ydimension set opt(cp) "connection_pattern" ;# Connection pattern set opt(sc) "scenario_file" ;# Scenario of simulation set opt(ifqlen)50 ;# Max packet in ifq set opt(nn) 50 ;# Number of mobilenodes set opt(stop) 900 ;# Time of simulation end set opt(rp) DSDV ;# Routing protocol set opt(nout) "nam_out.nam" ;# Nam out set opt(tout) "trace_out.tr" ;# Trace out # Trace Options set opt(AgentTrace) ON set opt(RouterTrace) ON set opt(MacTrace) OFF set opt(MovementTrace) ON # Procedure proc usage { argv0 } { puts "Usage: $argv0" puts "\tOptional arguments: \[-nn nodes\] \[-x MAXX\] \[- y MAXY\] \[-rp Routing protocol\] \[-cp conn pattern\] \[-sc scenario\] \[-stop sec\] \[-ifq interface queue\] \[-nout namout\] \[-tout traceout\]\n" } proc getopt {argc argv} { global opt lappend optlist nn x y rp cp sc stop ifq nout tout for {set i 0} {$i < $argc} {incr i} { set arg [lindex $argv $i] if {[string range $arg 0 0] != "-"} continue 79 set name [string range $arg 1 end] set opt($name) [lindex $argv [expr $i+1]] } } proc create-god { nodes } { global ns_ god_ set god_ [new God] $god_ num_nodes $nodes } proc stop {} { global ns_ f nf $ns_ flush-trace close $f close $nf } # Main Program # Get parameter from command getopt $argc $argv usage $argv0 puts "Topo: x=$opt(x), y = $opt(y)" puts "Routing Protocol: $opt(rp)" puts "Number nodes: $opt(nn)" puts "Stop at: $opt(stop)" puts "Scenario: $opt(sc)" puts "Connection pattern: $opt(cp)" puts "Nam out: $opt(nout)" puts "Trace out: $opt(tout)" puts "Interace queue type: $opt(ifq)" # Initialize Global Variables set ns_ [new Simulator] set topo [new Topography] # Use the new wireless trace file format $ns_ use-newtrace # Trace set f [open $opt(tout) w] set nf [open $opt(nout) w] $ns_ trace-all $f $ns_ namtrace-all-wireless $nf $opt(x) $opt(y) # Setup topography 80 $topo load_flatgrid $opt(x) $opt(y) puts "Loading topography..." # Create nn mobilenodes and attach them to the channel create-god $opt(nn) puts "Creating gods..." # Configure the nodes $ns_ node-config -adhocRouting $opt(rp) \ -llType $opt(ll) \ -macType $opt(mac) \ -ifqType $opt(ifq) \ -ifqLen $opt(ifqlen) \ -antType $opt(ant) \ -propType $opt(prop) \ -phyType $opt(netif) \ -channelType $opt(chan) \ -topoInstance $topo \ -agentTrace ON \ -routerTrace ON \ -macTrace OFF \ -movementTrace ON \ for {set i 0} {$i < $opt(nn)} {incr i} { set node_($i) [$ns_ node] } # Define node initial position in nam for {set j 0} {$j < $opt(nn)} { incr j } { $node_($j) namattach $nf # 30 defines the node size for nam $ns_ initial_node_pos $node_($j) 30 } # Source the Connection and Movement scripts puts "Loading connection pattern..." source $opt(cp) # Tell all the nodes when the simulation ends for {set k 0} {$k < $opt(nn) } { incr k } { $ns_ at $opt(stop) "puts \"stop node $k ...\";$node_($k) reset"; } 81 # Loading sccenario file puts "Loading scenario file begin..." source $opt(sc) puts "Loading scenario file complete..." # Ending nam and the simulation $ns_ at $opt(stop) "puts \"Nam end wireless...\";$ns_ nam-end- wireless $opt(stop)" $ns_ at $opt(stop) "puts \"Stop simulation...\";stop" $ns_ at $opt(stop).1 "puts \"end simulation\" ; $ns_ halt" # Run simulation puts "Starting Simulation..." $ns_ run 2. average_routing_packets.tpl # File: average_routing_packets.pl # Author: Doan Cao Thanh # Purpose: Calculate average routing packets for finding path (arp) # Type: perl average_routing_packets.pl # Get paratmeter $infile = $ARGV[0]; $pause_time = $ARGV[1]; # Constructor for variable $count = 0; $average_rp = 0; # Process input file open (DATA,"<$infile") || die "Can't open $infile $!"; @x = split(' '); while() { @x = split(' '); if (($x[0] eq "s" || $x[0] eq "f") && $x[18] eq "RTR" && ($x[34] eq "AODV" || $x[34] eq "DSR" || $x[34] eq "DSDV" || $x[34] eq "undefined" || $x[34] eq "message")){ #Check send or forward || undefined=olsr $count++; } } if($count == 0){ $average_rp = 0; }else{ 82 $average_rp = $count/900; } print STDOUT "$pause_time\t $average_rp\n"; close DATA; exit(0); 3. normalized_routing_overhead.pl # File: normalized_routing_overhead.pl # Author: Doan Cao Thanh # Purpose: Calculate normalized routing overhead (nro) # Type: perl normalized_routing_overhead.pl # Get paratmeter $infile = $ARGV[0]; $pause_time = $ARGV[1]; # Constructor for variable $count_pkt_routing = 0; $count_pkt_data = 0; # Process input file open (DATA,"<$infile") || die "Can't open $infile $!"; @x = split(' '); while() { @x = split(' '); if (($x[0] eq "s" || $x[0] eq "f") && $x[18] eq "RTR" && ($x[34] eq "AODV" || $x[34] eq "DSR" || $x[34] eq "DSDV" || $x[34] eq "undefined" || $x[34] eq "message")){ #Check send or forward || undefined=olsr $count_pkt_routing++; } if (($x[0] eq "s" || $x[0] eq "f") && $x[18] eq "AGT" && $x[34] eq "cbr"){ #Check send or forward $count_pkt_data++; } } $normalized_routing_overhead = $count_pkt_routing/($count_pkt_data+$count_pkt_routing); print STDOUT "$pause_time\t $normalized_routing_overhead\n"; close DATA; exit(0); 4. route_discovery_aodv.pl # File: route_discovery_aodv.pl # Author: Doan Cao Thanh 83 # Purpose: Calculate average time for determine route discovery in AODV protocol (rdt) # Type: perl route_discovery_aodv.pl # For AODV # -P aodv -Pt 0x2 -Ph 4 -Pb 28 -Pd 2 -Pds 73 -Ps 1 -Pss 72 -Pc REQUEST # 43,44 : -P aodv # 45,46: -Pt 0x2 Type # 47,48: -Ph 4 Hop Count # 49,50: -Pb 28 Broadcast ID # 51, 52: -Pd 2 Destination # 53, 54: -Pds 73 Destination Sequence Number # 55, 56: -Ps 1 Source # 57, 58: -Pss 73 Source Sequence Number # 59,60: -Pc REQUEST Operation # -P aodv -Pt 0x4 -Ph 1 -Pd 2 -Pds 42 -Pl 10.000000 -Pc REPLY : Khong có Pb, Pss + co them Pl # -P aodv -Pt 0x8 -Ph 1 -Pd 2 -Pds 0 -Pl 0.000000 -Pc ERROR: Khong co Pb, Pss + co them Pl # 49, 50: -Pd 2 Destination # 51, 52: -Pds 73 Destination Sequence Number # 53,54: Pl 10.000000 Lifetime # 55,56 : -Pc REPLY|ERROR Operation # Get paratmeter $infile = $ARGV[0]; $pause_time = $ARGV[1]; # Constructor for variable @send = (0..0); @source = (0..0); @recv = (0..0); $num = 0; # Process input file open (DATA,"<$infile") || die "Can't open $infile $!"; @x = split(' '); $max_broadcastID = 0; while() { @x = split(' '); $event_ = $x[0]; $time_ = $x[2]; $type_ = $x[49]; if($type_ eq "-Pb"){ #BroadcastID and RouteRequest 84 $broadcastID_ = $x[50]; $max_broadcastID = $broadcastID_ if ($max_broadcastID < $broadcastID_); if($event_ == "s" && $x[18] eq "RTR" && $x[34] eq "AODV" && !$send[$max_broadcastID]){ $source_ = $x[56]; #Ps 1 $send[$max_broadcastID] = $time_; $source[$max_broadcastID] = $source_; } }elsif($type_ eq "-Pd"){ #Determine Hs and Hd $hs_ = $x[4]; $hd_ = $x[6]; if($hs_ eq $hd_ && $hs_ eq $source[$max_broadcastID]){ if($event_ == "r" && $x[18] eq "RTR" && $x[34] eq "AODV" && !$recv[$max_broadcastID]){ $recv[$max_broadcastID] = $time_; } } }else{ #Do nothing } } close DATA; $delay = 0; for($count=0;$count<=$max_broadcastID;$count++){ if($send[$count] && $recv[$count]){ $send_ = $send[$count]; $recv_ = $recv[$count]; $interval_ = $recv_ - $send_; $delay += $interval_; $num++; } } if($num == 0){ $avg_delay = 0; }else{ $avg_delay = $delay / $num; } print STDOUT "$pause_time\t $avg_delay\n"; exit(0); 5. route_discovery_dsr.pl 85 # File: route_discovery_dsr.pl # Author: Doan Cao Thanh # Purpose: Calculate average time for determine route discovery in dsr (rdt) # Type: perl route_discovery_dsr.pl # For DSR # -P dsr -Ph 5 -Pq 0 -Ps 2 -Pp 01-Pn 2 -Pl 5 -Pe 1->2 -Pw 0 - Pm 0 -Pc 0 -Pb 0->0 # 43,44: Type -P dsr # 45,46: -Ph 5 Number Of Nodes Traversed # 47,48: -Pq 0 Routing Request Flag # 49,50: -Ps 2 Route Request Sequence Number # 51,52: -Pp 1 Routing Reply Flag # 53,54: -Pn 2 Route Request Sequence Number # 55,56: -Pl 5 Reply Length # 57,58: -Pe 1->2 Source->Destination Of Source Routing # 59,60: -Pw 0 Error Report Flag (?) # 61,62: -Pm 0 Number Of Errors # 63,64: -Pc 0 Report To Whom # 65,66: -Pb 0->0 Link Error From Link A to Link B # Get paratmeter $infile = $ARGV[0]; $pause_time = $ARGV[1]; # Constructor for variable @send = (0..0); @source = (0..0); @recv = (0..0); $num = 0; $max_sequence_number = 0; # Process input file open (DATA,"<$infile") || die "Can't open $infile $!"; @x = split(' '); while() { @x = split(' '); $event_ = $x[0]; $time_ = $x[2]; if($x[18] eq "RTR" && $x[34] eq "DSR") { $sn_ = $x[50]; $max_sequence_number = $sn_ if ($max_sequence_number < $sn_); 86 if($event_ eq "s" && $x[56] eq 0 && $x[48] eq 1 && $x[52] eq 0 && !$send[$sn_]){ $send[$sn_] = $time_; $source[$sn_] = $x[4]; #Hs } if($event_ eq "r" && $x[56] ne 0 && $x[48] eq 0 && $x[52] eq 1 && !$recv[$sn_] && $max_sequence_number eq $sn_){ $hs_ = $x[4]; $hd_ = $x[6]; if($hs_ eq $hd_ && $hs_ eq $source[$sn_]){ $recv[$sn_] = $time_; } } } } close DATA; $delay = 0; for($count=0;$count<=$max_sequence_number;$count++){ if($send[$count] && $recv[$count]){ $send_ = $send[$count]; $recv_ = $recv[$count]; $interval_ = $recv_ - $send_; $delay += $interval_; $num++; } } if($num == 0){ $avg_delay = 0; }else{ $avg_delay = $delay / $num; } print STDOUT "$pause_time\t $avg_delay\n"; exit(0);