Tiểu luận Thuật toán mentor II

ĐẠI HỌC BÁCH KHOA HÀ NÔI VIỆN ĐIỆN TỬ - VIỄN THÔNG Đề tài: THUẬT TOÁN MENTOR II Giảng viên hướng dẫn: Trần Ngọc Lan Sinh viên thực hiên: 1. Lê Thái Hưng KSTN-ĐTVT-K52 2. Trần Hữu Cương KSTN-ĐTVT-K52 3. Phạm Văn Chí KSTN-ĐTVT-K52 4. Bùi Thị Thế Hà KSTN-ĐTVT-K52 Hà Nội, tháng 11 năm 2011 Mục Lục 1. Giới Thiệu ................................................................................................................................................. 3 YÊU CẦU CỦA BÀI TẬP ........................................................................................................................... 5 2. Lý thuyết ................................................................................................................................................... 6 2.1 Thuật toán Mentor ......................................................................................................................... 6 2.1.1 Xác định node backbone và node trung tâm ......................................................................... 6 2.1.2 Chuyển yêu cầu node sang xương sống. ............................................................................... 7 2.1.3 Xây dựng cây Prim-Dijkstra với tham số α........................................................................... 8 2.2 Thuật toán Mentor II ..................................................................................................................... 8 2.2.1 Đặt vấn đề .................................................................................................................................... 8 2.2.2 ISP(Incremental Shortest Path) ............................................................................................. 9 3. Triển khai thuật toán ........................................................................................................................... 13 3.1. Tổng quan về kiến trúc .................................................................................................................... 13 3.2. Xây dựng đồ thi cơ sở ...................................................................................................................... 13 3.2.1 Class Node ................................................................................................................................. 13 3.2.2 Class Arc ................................................................................................................................... 14 3.2.3. Class Graph ............................................................................................................................... 14 3.3. Thuật toán ................................................................................................................................... 15 3.3.1 classMentor ......................................................................................................................... 15 3.3.2 Class Prim – Dijkstra .......................................................................................................... 16 3.3.3 Class Floyd – Warshall ...................................................................................................... 16 3.3.4 Class ISP ............................................................................................................................. 16 3.4. Form chính ....................................................................................................................................... 18 4 Kết luận ............................................................................................................................................... 21 2 1. Giới Thiệu Như ta đã biết, “viễn thông” được hiểu là cách trao đổi dữ liệu thông qua kỹ thuật điện, điện tử và các công nghệ hiện đại khác. Và “hệ thống viễn thông” là tập hợp các trang thiết bị kỹ thuật để cung cấp dịch vụ viễn thông cho người sử dụng. Ngay từ ngày xa xưa, những người tiền sử đã biết dùng khói để báo hiệu, những người thổ dân ở những hòn đảo xa xôi dùng các cột khói để liên lạc, báo hiệu và truyền tin. Nhưng “viễn thông” được chính thức sử dụng khi con người phát minh ra điện báo và điện thoại. Công nghệ viễn thông từ đó ngày càng phát triển nhanh chóng và vượt bậc, ứng dụng trong mọi lĩnh vực. Trên quy mô xã hội, viễn thông đã làm nên một hệ thần kinh thông minh nhạy bén trên trái đất, làm thay đổi bộ mặt, tính cách của từng quốc gia và tự trong nó hình thành lên một mạng lưới liên kết mỗi người của mỗi quốc gia trên trái đất. Sự hội tụ công nghệ trong lĩnh vực viễn thông cùng sự phát triển tăng trưởng mạnh của kinh tế - xã hội, nhu cầu sử dụng cũng như truyền dữ liệu của con người cũng tăng lên theo hàm số mũ và ngày càng trở nên phức tạp, có khuynh hướng kỹ thuật cao với chất lượng cao. Vì vậy, việc tổ chức một mạng viễn thông đáp ứng được nhu cầu ấy và phát triển tổ chức mạng lưới này thành một thành phần cơ bản quan trọng của xã hội thông tin hóa cao trong tương lai nữa là không hề đơn giản, nó đóng một vai trò rất quan trọng. Để giải quyết bài toán trên, ta nhìn hệ thống viễn thông trên cả phương diện phần cứng và phần mềm:  Về phương diện phần cứng, hệ thống viễn thông gồm các thiết bị như: Thiết bị đầu cuối thông tin, thiết bị chuyển mạch, thiết bị truyền dẫn.  Về phương diện phần mềm, hệ thống viễn thông cho biết các phần cứng liên hệ với nhau thế nào ( Topo mạng, với topo mạng ta sẽ phân biệt được mạng AN(Access Network) và mạng lõi), các giao thức mạng, các giao thức để liên kết, giao thức để trao đổi thông tin (giữa hai giao thức này có thể tách rời, có thể kết hợp với nhau), quản lý và khai thác mạng. Trên phương diện phần mềm, để xây dựng mạng, ta phải xây dựng được cấu hình của các phần tử mạng. MENTOR (Mesh Network Topology Optimization Routing) là một thuật toán rất hữu ích cho việc thiết kế mạng thông tin vì nó không phụ thuộc vào đặc điểm của bất kỳ một công nghệ hay kiến trúc mạng nào. Nó chỉ phụ thuộc vào nguyên tắc thiết kế mạng. MENTOR có thể ứng dụng cho nhiều loại mạng, đặc biệt là mạng ATM (Asynchronous Transfer Mode). Và chương trình MENTOR là một ứng dụng tin học trong việc thiết kế Topology cho mạng bằng chính thuật toán MENTOR. 3 Trong đề tài này yêu cầu chúng em viết một chương trình MENTOR như thế. Chương trình chúng em viết trong thời gian ngắn và kiến thức có hạn nên có rất nhiều những hạn chế nhất định như chỉ có tính chất mô phỏng, các giả thiết, điều kiện chưa hoàn toàn giống với yêu cầu thực tế. Tuy nhiên, chúng em hy vọng chương trình này cũng giúp mọi người nắm được quá trình xây dựng Topology cho mạng. Trong quá trình thực hiện bài tập lớn, chúng em xin cảm ơn sự tận tình giúp đỡ của cô Trần Ngọc Lan đã giúp chúng em hoàn thành bài tập này. Chúng em rất mong nhận được những lời khuyên từ thầy để chúng em có thể khắc phục được những cái chưa làm được trong đề tài để chúng em có thể hiểu sâu sắc hơn về thuật toán cũng như chương trình MENTOR trong xây dựng Topology cho mạng viễn thông, đồng thời hiểu rõ hơn về môn học Tổ chức và quy hoạch mạng viễn thông. Chúng em xin chân thành cảm ơn cô! 4 YÊU CẦU CỦA BÀI TẬP Viết một phần mềm tạo topology mạng viễn thông theo thuật toán MENTOR 2. nn : Số lượng nút trong mạng: Cost: Chi phí kết nối giữa các nút là một ma trận [nxn] Req: Ma trận [nxn] yêu cầu Pc, W, R/D: Các tham số xác định nút BackBone α: Tham số xác định cây γ : Hệ số sử dụng băng thông Cmax [nxn]: Giá trị tối đa dung lượng của liên kết giữa các nút( hiệu dụng) - Tìm cây kết nối các nút, α cho biết cây là dạng MST hay PST, MENTOR. - Tổng chiều dài cây, chiều dài đường đi - Direct link: Tìm kết nối Direct link - Đường đi trên cây Tất cả thể hiện trên màn hình đồ họa. 5 Mentor Bắt đầu Xác định node backbone thoả mãn điều kiện nw(i) > w Xác định MAXCOST Xác định node truy cập của node backbone đã xác định Tìm node trung tâm của node chưa phân loại, tính merrit từ đó tìm node backbone trong tập chưa xác định đó, cập nhật lại danh sách backbone và node truy cập 2. Lý thuyết 2.1 Thuật toán Mentor 2.1.1 Xác định node backbone và node trung tâm Tính moment rồi xác định node root Kết thúc Hình 2.2.1 Lưu đồ thuật toán xác định node backbone Bước 1: xác định node backbone thỏa mãn tiêu chuẩn trọng số: + Trọng số của một node là tổng của tất cả các lưu lượng vào và ra node + Trọng số chuẩn hóa dựa vào node i là NW(i) = W(i) / C +W là tham số + Node có NW(i) > W được chọn làm node xương sống Bước 2: xác định MAXCOST + MAXCOST = maxi,j cost(Ni,Nj) = maxi,j Bước 3: Xác đinh node truy cập của node backbone đã xác định + Tất cả các node không thảo mãn tiêu chuẩn trọng số và “gần” node xương sống sẽ được chọn làm node truy cập 6 + “ gần ” được định nghĩa là khi giá liên kết từ node truy cập “e” đến node xương sống là nhỏ hơn một phần của giá liên kết lớn nhất. cost(e,Ni) < MAXCOST * RPARM, hay < MAXCOST * RPARM. Bước 4: xác đinh node backbone và truy cập cho những node còn lại thuộc tập M + Tìm trung tâm của trọng lực (xctr, yctr). - xctr = - yctr = + Khoảng cách tới CG - dcn = - maxdc = max(dcn) - maxW = max (Wn) + Tính merit - merritn = + Phân loại các node còn lại - “merrit” đưa ra giá trị cân bằng giữa vị trí gần trung tâm và trọng số của nó. - Trọng số những node chưa được phân loại, chọn node có thưởng cao nhất và chuyển node này thành node xương sống. - Phân loại các node mới thành các node truy cập. - Cứ tiếp tục cho đến khi tất cả các node được phân loại. Bước 5: Tìm node trung tâm + lựa chọn node xương sống trung tâm với giá trị moment nhỏ nhất đến trung tâm - Moment(n) = 2.1.2 Chuyển yêu cầu node sang xương sống. 7 + xét ei là node truy cập của node bi, bi là node trước trong cây. Ví dụ xét e1,e2,b1và b2 nếu b1 = b2 thì không chuyển yêu cầu của e1 và e2 sang b1 và b2, và ngược lại. Hình 2.1.2 ví dụ về chuyển yêu cầu 2.1.3 Xây dựng cây Prim-Dijkstra với tham số α + các node đầu vào là node backbone đã xác định ở trên và root là node trung tâm. + Thuật toán: - Nhãn Prim = minneighbors dist(node, neighbor) - Nhãn Dijkstra = minneighbors [dist(root, neighbor) + dist(neighbor, node)] - Nhãn Prim-Dijkstra = minneighbors [α* dist(root, neighbor) + dist(neighbor, node)] 2.2 Thuật toán Mentor II 2.2.1 Đặt vấn đề Sau khi chúng ta thiết kế xong mạng, chúng ta xem xét xem lưu lượng sẽ đi qua đâu. Đưa ra một vấn đề mà trung tâm chính là chất lượng hoạt động của thuật toán định tuyến. Nếu chỉ sử dụng thuật toán Prim – Dijkstra, số lượng liên kết là ít nhất mà vẫn đảm bảo có một và chỉ một đường đi duy nhất giữa 2 node bất kì. Tuy nhiên với thiết kế như thế, sẽ tồn tại những liên kết mà lưu lượng đi qua nó rất lớn, điều đó đồng nghĩa với việc không đảm bảo tính ổn định cho mạng 8 Hình 2.2.1ví dụ mạng backbone sau mentor 1 Như hình vẽ trên, ta có thể thấy liên kết giữa node 8 và 9 có lưu lượng đi qua lớn do yêu cầu từ các các node backbone 9, 2, 14 đến node backbone 8, 4. Trong khi đó, liên kết giữa 2 node 2 và 14 lại ít do chỉ có các yêu cầu đi từ node 14 đến các node còn lại. Để khắc phục điều này, chúng ta có thể thêm các liên kết trực tiếp giữa các node. Ví dụ, node 14 và node 4. Như vậy, một số yêu cầu từ một số node (VD: node 2, 14) sẽ đi qua liên kết mới này. Tuy nhiên, nếu thêm các liên kết trực tiếp này thì khả năng một số liên kết đã có từ trước sẽ giảm lưu lượng (VD: trong trường hợp này là liên kết 9 – 8, 9 – 2) đôi lúc lưu lượng này trở về 0. Hay nói cách khác, thuật toán định tuyển sẽ tìm thấy đường đi ngắn nhất nhưng đường đi đó có thể không tìm thấy đường khả thi cho thiết kê mạng của chúng ta. Như vậy, cần cải thiệt giải thuật mentor thêm các liên kết trực tiếp nhưng vẫn phải xem xét luôn đến giới hạn của thuật toán đinh tuyển. Kết quả là thuật toán Mentor II ra đời. 2.2.2 ISP(Incremental Shortest Path) 9 ISP + Đầu vào là các thông số Bắt đầu kết thúc thuật toán Mentor Xác định sp_dist[][], sp_pred[][]. i=0;S(i) J=0;D(j) no yes i< numBackbone yes no j< numBackbone Xác định S_list && D_list i++ Cập nhật sp_dist[][] && sp_pred[][] Tính maxL[n][m] Sắp xết theo thứ tự giản dần Đây là bước cải tiến để đáp ứng phần nào yêu cầu đã trình bày ở trên. Mục đích của thuật toán ISP là xác định tất cả những cặp có thể sử dụng liên kết trực tiếp thay cho các cặp có maxL[n][m] > D đường hiện thời. J++ Kết thúc Hình 2.2.2 lưu đồ thuật toán ISP 2.2.2.1 Ma trận khoảng cách – thuật toán Floyd Warshall Để thực hiện điều này ta cần có 2 ma trận 10 Khoảng cách đường ngắn nhất Shortest-path distances giữa 2 node i, j(sp_dist)nxn Ma trận con trỏ node trên đường đi ngắn nhất giữa 2 node i, j(sp_pred)nxn Hai ma trận này luôn được cập nhật sau mỗi lần thêm liên kết. Cách xây dựng ma trận này với đồ thị bất kì rất giống trong thuật toán Floyd – Warshall Hình 2.2.2.1 ví dụ xây dựng sp_dist[][] và sp_pred[][] 2.2.2.2 Thứ tự xem xét các cặp cạnh Chúng ta sắp xết các cặp cạnh theo thứ tự bước nhảy. Và coi đó là thứ tự cần xét xem có thêm liên kết trực tiếp hay không Hình 2.2.2.2 ví dụ về sắp xếp các cạnh theo thứ tự 2.2.2.3 Xét cạnh thêm vào Khi xem xét liệu có thêm liên kết trực tiếp giữa node nguồn S và node đích D độ dài liên kết SD = L. ta xây dựng s_list và d_list o s_list với ý nghĩa tập node “được hưởng lợi” nếu muốn đi đến node khác nếu dùng liên kết trực tiếp SD 11 o d_list với ý nghĩa tập node “được hưởng lợi” nếu muốn đi đến node khác nếu dùng liên kết trực tiếp DS Với ý nghĩa như trên, cách xây dựng s_list và d_list như sau: o Thêm node vào s_list nếu: sp_dist[node, s] + L < sp_dist[node, d] o Thêm node vào d_list nếu: sp_dist[node, d] + L < sp_dist[node, s] Hình 2.2.2.3 ví dụ xây dựng s_list[] và d_list[] Xem xét tất cả các cặp (ni, nj) trong đó ni thuộc s_list và nj thuộc d_list. Khi đó, lưu lượng (ni, nj) sẽ chuyển sang liên kết dự định nếu sp_dist[ni, s] + L + sp_dist[d, nj] < sp_dist[ni, nj] Độ dài lớn nhất cho có thể ấn định lưu lượng (ni, nj) để chuyển đi theo đường này là maxL = sp_dist[ni, nj] - sp_dist[ni, s] + sp_dist[d, nj] Điều này có nghĩa là nếu đo dài liên kết (ni, nj) ấn định trong khoảng (L, maxL) thì lưu lượng sẽ chuyển đi theo đường đi SD mới này Với mỗi cặp (ni, nj) ta sẽ có số maxL. Ta sắp xếp các cặp này theo thứ tự từ trên xuống maxL(P1) = 2000 maxL(P2) = 1800 maxL(P3) = 1800 maxL(P4) = 1700 Ở đây, nếu chọn giá trị cạnh là bao nhiêu sẽ quyết định có bao nhiêu cặp (ni, nj) có thể sử dụng liên kết này. Ví dụ SD = 1750 thì có các cặp P1, P1, P3 sẽ dùng liên kết mới này. 12 3. Triển khai thuật toán 3.1. Tổng quan về kiến trúc 3.2. Xây dựng đồ thi cơ sở 3.2.1 Class Node + Thuộc tính: o public const int isRoot = -1; o public const int unknown = -2; o public const int drawIndex = 0x10; o public const int drawWeigh = 0x20; // thong so co ban o public int index; // thu tu node o public int x, y; // toa do o public double weigh; // trong luong nut o public int priority; // >=0 neu la nut truy nhap, = index la backbone, -1 neu la goc, - neu chua xac dinh // Ket noi voi cac nut khac o public int numNode; o public List otherNodes; o public List send, recv; o public List distance; o public List connected; + Operator: o public Node(int _index, double _weigh, int _priority = Node.unknown, int _x = 0, int _y = 0, int _numNode = 0, List _otherNodes = null,  List _send = null, List _recv = null, List _distance = null, List _connected = null) {} //hàm tạo o public bool IsOne(Node other, int r = 50) {} o public void SetPosition(int _x, int _y) {} o public double GetDistance(Node Other) {} // Lấy tọa độ thực trên Decac(chưa bị thay đổi bởi mentor) o public void ConnectNodes(Node Other) // chi dung trong ham CreateNodes. nhu vay se dung thu tu luon - chu y la no phai connet voi chinh minh o public void DrawNode(Graphics Grfx, int draw, double div = 2, int r = 7) {} //vẽ node // Hàm này sẽ hiển thị node với màu sắc của node và số thứ tự tương ứng với node 13 3.2.2 Class Arc + Thuộc tính: o public Node destination, source; //so thu tu 2 diem source, destination o public double distance; //do dai canh: distance o public double c; //dung luong 1 lien ket o public double ratio; //dung luong cuc dai ung voi moi lien ket (tinh theo %) o public double capacity; //dung luong tren canh nay voi moi lien ket capacity = c * ratio = 2 * 60% o public double flow; //tong luu luong tren canh nay: flow o public int paths; //so luong lien ket song song: paths o public int priority; o public const int drawDist = 0x01; o public const int drawCap = 0x02; o public const int drawFlow = 0x04; o public const int drawPaths = 0x08; + Operator: o public Arc(Node _source, Node _destination, double _flow = 0.0, double _c = 2.0, double _ratio = 0.6, int _priority = Node.unknown) {} // hàm tạo o public void DrawArc(Graphics Grfx, int div = 2) {} // vẽ cạnh o public void DrawParameter(Graphics Grfx, int draw, int div = 2, int r = 8) {} //vẽ cạnh, hiển thi các thông số cạnh 3.2.3. Class Graph + Thuộc tính: o const int MAX_X = 1500, MAX_Y = 1500; o public List LN; o public List LA; o public int numNode = 0, numArc = 0; o public double cost = 0.0; o public int root = -1; o private Random rd = new Random(); + Operator: o public Graph(){} // hàm tạo 14 o public void CreatNodes(int _numNode) {} // Khởi tạo node trên mặt phẳng tọa độ cùng các tham số tương tự class node o public void AddNode(Node node) {} // Thêm node mới vào đồ hình o public void ChangeDistNode(Node n1, Node n2, double dist) {} //Thay đổi khoảng cách giữa các node o public void DeleLightBluelArcs() {} o public void AddArc(Arc arc) {} o public void AddArc(Node source, Node destination, double flow = 0.0) {} // Thêm cạnh với các tham số cạnh: node nguồn, node đich, flow o public void ChangeFlowArc(Arc arc, double flow) {} // Thay đổi flow o public void ChangePriorityArcs() {} o public void DrawPath(Graphics Grfx, List nodes, int div = 2) {} // vẽ cạnh o public void CopyFromGraph(Graph _graph) {} o public void CopyToGraph(Graph _graph) {} o public void AllCopyFromGraph(Graph _graph) {} // copy toàn bộ graph tới từng vùng nhớ o public void ClearGraph() {} o public double TotalCost() {} // Tính tổng cost o public void DrawGraph(Graphics Grfx, int draw, int div = 2) {} o protected int Compare(Arc x, Arc y){} // so sánh các cạnh o public void SortDistArc(List Arcs){} // sắp xếp các cạnh 3.3. Thuật toán 3.3.1 classMentor + Kế thừa từ class Graph + Thuộc tính o private double[] merit; o private double[] moment; o private double[] dc; o private double W; o private double C; o private double R; o private double MAXCOST = 0; + Operator o private void FindAcessNode(Node node) {} 15 //chua add canh nhe. moi chi chinh nut truy cap thoi o public void Process(Graph _graph, double _W = 4.0, double _C = 2.0, double _R = 0.3) {} // hàm này có là xác định node backbone và node trung tâm o public Mentor(){} // hàm tạo 3.3.2 Class Prim – Dijkstra + Thuộc tính: o private int[] convertIndex; //anh xa nguoc. tu index cua node => thu tu luu trong List node (chu y la gio no khong theo thu tu) o const int vc = 2000000000; o private double alpha; o private int start; o private double[] label; o private bool[] f