Khóa luận Tối ưu hóa topology trong mạng ad - Hoc

Các node sẽ di chuyển dọc theo những con đường theo hai hướng. Khi node di chuyển đến một chỗ cắt, nó sẽ chọn ngẫu nhiên một con đường, có thể là đi thẳng theo hướng như ban đầu hoặc có thể rẽ phải hoặc rẽ trái. Tương tự như mô hình FreeWay tốc đô hiện thời của node phụ thuộc vào tốc độ trước đó của node theo bước thời gian. Ví dụ thứ 3 của mô hình Map- based là mô hình the Obstacle mobility, trong mô hình này bản đồ được tạo ra đầu tiên là thêm các vật cản (những tòa nhà chẳng hạn) những trở ngại được thêm vào có thể được lấy một cách ngẫu nhiên hoặc dựa trên bản đồ thực tế. Một khi các công trình xây dựng được triển khai những con đường nối những công trình này sẽ được tạo ra và những node sẽ được giả định di chuyển theo những con đường này. Một tính năng thú vị của mô hình này đó là những vật cản cũng được tính toán cho việc mô phỏng tín hiệu được lan truyền trong môi trường. Nói cách khác mô hình này còn giả định được những tín hiệu sẽ bị cản bởi các vật cản trong môi trường Group-based mobility: Tất cả những mô hình được giới thiệu từ trước đều mô phỏng sự di chuyển của từng cá thể. Tuy nhiên trong nhiều tình huống các node có thể di chuyển theo một nhóm (ví dụ như một nhóm du lịch di chuyển trong thành phố) Group-based Mobility được tạo ra để mô hình những tình huống như trên.Trong mô hình Group-based Mobility một nhóm nhỏ các node mạng được coi như là những trưởng nhóm (group leaders). Những node còn lại sẽ được gán ngẫu nhiên với những trưởng nhóm tạo thàn một nhóm.Đầu tiên các nhóm trưởng sẽ ngẫu nhiên phân phối vùng triển khai R và các thành viên trong nhóm sẽ có vị trí ngẫu nhiên trong vùng R và là ‘hàng xóm’ của trưởng nhóm.Sau đó các trưởng nhóm sẽ di chuyển theo một mô hình đã được giới thiệu ở phía trên, Chẳng hạn như là RWP hay RDM. Các thành viên trong nhóm sẽ làm theo người đứng đầu, các thành viên này sẽ có hướng và tốc độ theo hướng và tốc độ của trưởng nhóm. Khi hai nhóm giao nhau, một thành viên bất kỳ có thể rời nhóm của nó và gia nhập vào một nhóm khác theo một xác suất đã biết. Chi tiết về mô hình Group-based Mobility có thể tham khảo ở một số tài liệu khác như Hong et al. 1999; Wang and Li 2002 Chương 3. Tối ưu hóa Topology 3.1. Vấn đề về vùng ảnh hưởng Trong chương này chúng ta sẽ xem xét các vấn đề để phân bố được một cấp độ truyền để tạo ra một đồ thị truyền thông với một khoảng thời gian trong khi sẽ giảm thiểu được sự tiêu thụ năng lượng. Vấn đề này được hiệu như là một vấn đề của vùng ảnh hưởng 3.1.1. Định nghĩa vấn đề Chúng ta nhắc lại rằng, thiết lập cho tập hợp những node N trên mạng, một vùng ảnh hưởng cho N là một hàm RA, hàm này sẽ gán cho mỗi node thuộc N một vùng ảnh hưởng RA(u) với 0 < RA(u) ≤ rmax với rmax là vùng ảnh hưởng lớn nhất. Chú ý rằng, dưới giả thuyết là mô hình Path Loss được sử dụng cho mọi Node, và hiệu ứng Shadowing/fading không được xem xét, và vùng truyền (Transmitting Range) và cấp độ truyền (transmit power level) là những khái niệm tương đương. Hàm RA trước đây được định nghĩa như là các quy tắc về phạm vi thay vi sức mạnh và chúng ta vẫn giữ những quy ước này. Những vấn đề về Range Assigment được định nghĩa như sau: Định nghĩa 3.1.1(Vấn đề RA): Cho N là tập hợp những node trong không gian d chiều (d= 1, 2, 3) Một hàm range assigment được xác định tương đương như là một đồ thị truyền thông với những kết nối mạnh, và là hàm kết nối tất cả các RA với một khoảng cách nhỏ nhất, với là độ suy giảm cường độ theo khoảng cách. Chi phí đo c() được sử dụng trong định nghĩa vấn đề RA là tổng cấp độ truyền( Transmit Power levels) được sử dụng tại các node trong mạng. Vì vậy một vấn đề của RA có thể thực sự được bắt đầu với việc tìm một RA ‘minimal’ với những node, với RA này các node sẽ kết nối với nhau để tạo thành một đồ thị truyền thông, và minimal ở đây có thể được hiểu là ‘chi phí năng lượng nhỏ nhất’. Bên cạnh việc giảm thiểu sự tiêu thụ năng lượng việc kết nối RA với sự tiêu thụ năng lượng nhỏ này sẽ giúp phần tăng thêm khả năng của mạng 3.1.2. Vấn đề RA trong những mạng một chiều (One-Dimensional Networks). Trong phần này chúng ta sẽ giới thiệu một số thuật toán cho việc tìm kiếm những giải pháp cho vấn đề RA.Trước khi trình bày thuật toán chúng ta cần định nghĩa một cách sơ bộ Cho N là một tập hợp những điểm (Node) nằm trên một đường thẳng.Không mất tính tổng quát, chúng ta giả sử rằng các node được sắp xếp tăng dần tùy thuộc theo tọa độ trong không gian, chẳng hạn như u1 là node bên trái nhất và un là node bên phải nhất. Cho một bộ những node và một RA, chúng ta gọi những cạnh (ui, uj) trong đồ thị truyền thông thu được là một backward nếu mà i > j, có nghĩa là cạnh đi từ phải sang trái. Với bất kỳ i, j nào (1 i < j n) chúng ta định nghĩa tập hợp Ei,j gồm tất cả các cạnh backward có điểm đầu cuối thuộc {ui , uj}, Ei,j = {(us, ur) : i r < s j} Một số cạnh backward được giới thiệu trong hình bên dưới. (Những cạnh bôi đen là những cạnh backward) Hình 4: Các cạnh backward Thuật toán cho việc tìm kiếm một giải pháp tối ưu dựa trên nền tảng là những phép đệ quy. Cho một RA tối ưu kết nối cho các node (u1, uk) với 1 k <n , sau đó chúng ta sẽ xây dựng được một RA tối ưu kết nối cho (u1, uk+1). Tư tưởng chính của thuật toán này là khi chúng ta đã có một RA tối ưu với k node là RAk thì RA tiếp theo có thể được xác định. Giả sử chi phí của RAk là 0 (giả thiết, nghĩa là c(RAk) cũng bằng 0) và khi có thêm một node gia nhập thêm vào thì chi phí của RAk+1 sẽ được tăng lên một giá trị đã được xác định điều này được thể hiện trong định nghĩa sau: Định nghĩa 3.2.1 (RA increamental cost) Cho N = {u1, . . . , un} là một tập hợp các node và E là bộ những cạnh giữa những node trong N. RA được sinh ra bởi E được gọi là RAE , RAE là “minimal assignment” khi RAE(ui)với bất kỳ một cạnh có hướng (ui, uj) E.Chi phí tăng thêm của range assignment liên quan tới E được gọi là cE(RA), được xác định như sau: cE(RA) = . Chúng ta gọi những cạnh trong E là ‘free of cost ’ đối với range assignment RA. Những giả thiết dựa trên nền tảng của thuật toán quay lui, với bất kỳ j k và bất kỳ l k, tồn tại một Range assigment RA với một chi phí nhỏ nhất trong số các đồ thị truyền thông sẽ có các thuộc tính sau đây: - Giữa một cặp node bất kỳ đều có đường tồn tại - Có một cạnh nối trực tiếp giữa ui và ul, l<=i <=k - Với bất kỳ một cạnh (backward) trong E thì đều free of cost với RA Cho (N’, E) là một đồ thị kết nối tất cả các node N’ và có các cạnh là E, và N’ ⊂ N, và khi đồ thị này nhận thêm một node v trong N chúng ta gọi là reciever node. Một Range assigment được gọi là total cho ((N’ , E), v) khi và chỉ khi: - Đồ thị được tạo ra bởi N’ node thu được bằng cách thêm vào các cạnh của E tạo nên một kết nối mạnh nghĩa là (RA(ui) ≥ δ(ui, uj )) - Đều tồn tại cạnh giữa (u,v ) với ui∈ N và kết nối giữa v và ui là mạnh nghĩa là (RA(ui) ≥ δ(ui, v )) Chi phí của cho tổng Range assigment của ((N’ , E), v) là chi phí được tăng thêm liên quan đến RAE, hay như định nghĩa về RA increamental cost là cE(RA). Như vậy tổng cộng range assigment cho ((N’ , E), v) với một chi phí nhỏ nhất được gọi là tối ưu . Trong phần sau đây chúng ta gọi Feas((N’ , E), v) là tập hợp những range assigment Feas((N’ , E), v) và Opt ((N’ , E), v) là tập hợp những optimal range assigment. Cuối cùng, cho u ∈ N và một đại lượng xác thực là r, chúng ta coi rằng Opt((N’, E), v, (u, r))) là tập hợp những range assigment với chi phí nhỏ nhất và RA(u) = r. Thuật toán Optimal1dRA để tìm ra giải pháp tối ưu cho vấn đề RA được trình bày sau đây: 1. Khởi tạo 1.1 Cho RAi có Range assigment là RAi (u1) = δ(u1, ui), và RAi(u1) = 0 nếu i =0 1.2 Nếu không for i = 2 … n khởi tạo Opt(({u1}, ∅), ui) = RAi 2. Bước k 2.1 Giả sử chúng ta biết Opt(({u1, . . . , uk}, Ei,k), ul) ,với bất kỳ 1 i < k và k l n. 2.2 Với j, m bất kỳ , 1 ≤ j ≤ k + 1 ≤ m ≤ n 2.3. Xét tất cả các giá trị có thể của RA(uk+1) (tương tự với k+2 ) 2.4 for với mỗi giá trị của r, tìm một range assignment trong Opt(({u1, . . . , uk}, Ej,k+1), uk+1, (uk+1, r)) 2.5. Nếu có chi phí nhỏ hơn so với hiện thời cho j , m thì lưu RA 2.6. Kết thúc bước k, chúng ta biết một range assignment Opt(({u1, . . . , uk+1}, Ei,k+1), ul), với bất kỳ 1 ≤ i ≤ k + 1 ≤ l ≤ n 3. ở bước n Một Range assignment tối ưu chính là một trong Opt(({u1, . . . , un}, ∅), un) Tư tưởng chính của thuật toán này là: đầu tiên khởi tạo một RAi(u1) nếu i là 1 thì RA1(u1) = 0 Nếu i khác 1 thì tìm các RA tối ưu của u1 với bất kỳ 1 node khác. Trong bước đệ quy giả sử chúng ta đã biết Opt(({u1, . . . , uk}, Ei,k), ul) với bất kỳ 1 i k và k l n. với mỗi node thêm vào chúng ta tìm được một RA tối ưu khi thêm vào mỗi node đó Tại bước cuối cùng khi thêm một node cuối cùng chúng ta sẽ tìm được một RA tối ưu nhất cho toàn bộ node N. Các nhà nghiên cứu đã chứng minh được độ phức tạp của thuật toán này là O(n4). So sánh thuật toán Optimal1dRA khi tìm kiếm một RA tối ưu với giả thiết là các Transmitting Range là bằng nhau thì thuật toán sẽ đơn giản hơn rất nhiều . 3.1.3. Vấn đề RA trong mạng 2 và 3 chiều Trong phần trước, chúng ta đã phân tích được vấn đề RA trong mạng 1 chiều. So với vấn đề trong mạng 1 chiều thì vấn đề tính toán trở nên phức tạp hơn nhiều, sự tính toán này cũng là một vấn đề lớn trong mạng 2 và 3 chiều này. Mặc dù giải pháp cho mạng 2 và 3 chiều là một công việc khó khăn, nhưng một giải pháp tối ưu xấp xỉ có thể dễ dàng được tính toán bằng cách xây dựng một Minimum Spaining Tree (MST) trên các node. Sự xây dựng một RA được tiến hành như sau: 1. Cho N= {u1, . . . , un} là một tập hợp những điểm (Node) trong không gian mạng 2 hoặc 3 chiều 2. Xây dựng một đồ thị vô hướng G = (N, E), với các cạnh là (ui, uj) ∈ E 3. Tìm một MST của G 4. Xác đinh một RAT với RAT(ui) = MAXj|(ui,uj)∈Tδ(ui, uj). Một ví dụ về cây MST và tương ứng với những RAT được miêu tả trong hình bên dưới Hình 5: Minimum Spanning Tree Thời gian xây dựng RAT là O(n2) (Độ phức tạp của thuật toán khi xây dựng MST với n node) Định lý 3.2.3: (Kirousis et al. 2000) Cho một tập hợp những điểm (nodes) trong không gian 2 hoặc 3 chiều, và cho RAT được định nghĩa như trên, cho là một optimal range assignment với vấn đề RA thì c(RAT) < 2c(). Chứng minh: Việc chứng minh được thực hiện qua hai bước. Trước tiên chúng ta chứng minh c() lớn c(T) nghĩa là chi phí của RA lớn hơn chi phí cả MST. Và sau đó chúng ta sẽ chứng minh c(RAT) < 2c(). 3.1.4. Vấn đề về tính đối xứng Trong vấn đề về RA chúng ta đã quan tâm đến việc thiết lập một đồ thị giao tiếp với những kết nối mạnh. Từ việc những node có những vùng ảnh hưởng khác nhau, những liên kết vô hướng xuất hiện, và chúng có thể đảm bảo cho sự kết nối mạnh. Mặc dù việc triển khai việc liên kết không dây vô hướng là một công việc có thể thực thi được nhưng lợi ích mang lại của nó đang là một vấn đề phải nghi ngờ. Những vấn đề của liên kết không dây vô hướng được đề cập trong tài liệu Marina and Das 2002 Hầu hết các giao thức định tuyến cho mạng ad-hoc ( DSC, AODV) đều dựa trên nền tảng là sự ngầm định của liên kết không dây đều có tính 2 chiều. Điều này cũng đang được áp dụng tương tự với sự thực thi của tầng MAC trong chuẩn IEEE 802.11 nó chính là cơ sở của việc trao đổi các thông điệp RequestToSend/ClearToSend: Khi một node u muốn send một bản tin tới v trong transmitting range nó sẽ gửi một RTS tới v và sẽ đợi CTS từ v gửi lại. Nếu u không nhận được CTS trong một khoảng thời gian giới hạn nào đó, thì bản tin được gửi sẽ bị ngắt và sau đó nó sẽ cố gắng gửi lại sau một khoảng thời gian nào đó. Nếu liên kết gữa node u và node v là vô hướng, một trong hai bản tin RTS hoặc CTS là không nhận được và sự liên kết ở đây cũng là không có. Việc hỗ trợ liên kết vô hướng ngầm định rằng có những node trung gian sẽ đại diện cho u hoặc v nhận và gửi các bản tin RTS và CTS. Ngoài ra một cơ chế truy cập khác( ví dụ như cơ chế phát hiện xung đột thay vì tránh xung đột) cũng nên được sử dụng. Dù sao thì việc hỗ trợ liên kết không dây vô hướng sẽ tạo ra một cuộc cách mạng thay đổi những giao thức đang được thực thi hiện thời trong chuẩn IEEE 802.11 Những lý do trên đây là động cơ thúc đẩy các nhà khoa học nghiên cứu những hạn chế trong vấn đề RA, và điều chắc chắn rằng tính đối xứng bắt buộc phải được thêm vào trong đồ thị truyền thông tạo ra. Chi tiết hơn, hai vấn đề sau đây đã được định nghĩa và đã được nghiên cứu. 3.4.1 (Vấn về WSRA): Cho N là một tập hợp những node trong không gian d chiều, với d = 1, 2, 3. Cho RA là một vùng ảnh hưởng cho N và G là là một đồ thị liên thông có hướng. Đồ thị con đối xứng của G được xác định là GS, thu được bằng cách bỏ đi các liên kết có hướng, vấn đề WRSA là xác định một hàm Range assigment RA khi mà GS được kết nối và là nhỏ nhất với α là độ suy giảm cường độ theo khoảng cách. 3.4.2 Vấn đề SRA: Cho N là một tập hợp những node trong không gian d chiều, với d = 1, 2, 3. Một range assignmnet RA cho N được gọi là đối xứng nếu nó sinh ra một đồ thị liên thông trong đó đồ thị này chỉ bao gồm những liên kết 2 chiều. Đó là RA(ui) ≥ δ(ui, uj) ⇔RA(uj) ≥ δ(ui, uj). Vấn đề Symmetric Range Assignment (RSA) là xác định một hàm RA khi có một đồ thị liên thông có hướng được kết nối và là nhỏ nhất với α là độ suy giảm cường độ theo khoảng cách. Hình 6: SRA và WSRA Hình trên thể hiện sự khác nhau trong việc yêu cầu tính đối xứng trong vấn đề WSRA và SRA. Trong WSRA những liên kết vô hướng là được cho phép nhưng chúng không đại diện cho việc kết nối . Trong RSA tất cả những liên kết trong đồ thị liên thông phải có 2 hướng: node u , v và w phải tăng transmitting range để thỏa mãn những yêu cầu về tính đối xứng. Chú ý rằng những yêu cầu về tính đối xứng 2 phiên bản này của vấn đề: trong vấn đề WSRA(Weakly Symmetric Range Assignment) trong đồ thị liên thông có thể bao gồm những liên kết vô hướng tuy nhiên chúng không đại diện cho tính kết nối. Còn đối với vấn đề RSA đồ thị liên thông chỉ bao gồm các liên kết 2 chiều. Đây là một yêu cầu chính tron đồ thị liên thông.Các bạn có thể xem hình bên trên để có thể hiêu hơn. Động cơ thúc đẩy cho việc nghiên cứu WSRA bắt nguồn từ việc quan sát những gì thực sự quan trong trong việc thiết kế mạng ad-hoc đó là tạo nên một khung của mạng. Hay nói cách khác trong một mạng có thể có các liên kết tồn tại mà tính 2 chiều không được đảm bảo, những liên kết này có thể được bỏ qua khi mạng không có các kết nối này. 3.1.4.1. Vấn đề SRA trong mạng 1 chiều Trong trường hợp các node nằm trong cùng một đường thẳng, một SRA cho tập hợp các node đó có thể được xây dựng như sau: Sắp xếp các node theo tọa độ không gian của chúng, cho {u1, . . . , un} là kết quả của sự sắp xếp này. Gán cho node u1 một transmitting range δ(u1, u2) node un một transmitting range δ(un−1, un), và node ui một transmitting range bằng Max{δ(ui−1, ui),δ(ui, ui+1)} Bổ sung transmitting range vào một số node để đảm bảo tính đối xứng: với mỗi cạnh vô hướng(ui, uj) trong đồ thị liên thông được tạo ra bởi bước trước đó bằng cách thêm transmitting range vào node uj sao cho nó có thể tiếp cận được với ui, quá trình này được lặp lại cho đến khi tất cả các cạnh trong đồ thị đều có tính thuận nghịch. Chúng ta có thể nhìn thấy ngay được là, Range assignment RA được xây dựng tùy theo chiến lược mô tả ở phía trên, để tạo ra một đồ thị liên thông kết nối trong đó tất cả các liên kết đều có tính 2 chiều. Để chứng minh rằng RA này là tối ưu, thì trong khi quan sát rằng để đạt được kết nối thì node phải được kết nối với node bên phải và bên trái của node hàng xóm gần nó nhất. Hơn nữa các thủ tục tăng ở bước 3 sẽ tăng một transmitting range lên một giá trị nhỏ nhất để có thể thỏa mãn tính đối xứng của transmitting range. Độ phức tạp tính toán của thuật toán cho vấn đề được nêu ở phía trên là O(n log n),so sánh với độ phức tạp của thuật toán cho vấn đề về phiên bản không giới hạn là O(n4) thì độ phức tạp của thuật toán này là thấp hơn rất nhiều. Như vậy chúng ta có thể kết thúc vấn đề tính đối xứng trong range assignment với mạng 1 chiều. 3.1.4.2. Vấn đề SRA trong mạng 2 và 3 chiều Trong chương này, chúng ta sẽ cho thấy rằng, trái ngược với trường hợp trong mạng 1 chiều, trong mạng 2 và 3 chiều những điều kiện về tính đối xứng sẽ không làm ảnh hưởng tới độ phức tạp của việc tính toán những vấn đề. Người đọc sẽ thấy rằng sự chứng minh là khá dài dòng và phức tạp. Những khó khăn của việc chứng minh bắt đầu từ thực tế là khi nghiên cứu về tính phức tạp của các vấn đề mạng ad-hoc thì thì hình dạng của mạng là không thể được bỏ qua. Chúng ta đã chứng minh rằng những node có thể thực sự được đặt trong không gian 2 hay 3 chiều trong đó bất kỳ những trường hợp đặc biệt nào cũng có thể được chuyển thành vấn đề kiểm soát đặc biệt SRA. Việc này thường được thực hiện bằng cách sử dụng một geometric hay thuật ngữ hay gọi là gadget . Để dễ dàng hơn cho việc trình bày, giả sử α = 2, để chứng minh NP-hardness của SRA chúng ta biểu diễn mặt phẳng 2 chiều bằng một hàm đa thức thời gian. Hàm này sau đó sẽ được biểu diễn dưới một dạng hình học mô phỏng. Việc xây dựng một gadget được trình bày như sau: - Cho một mặt phẳng 2 chiều G, xây dựng một mặt phẳng trực giao với G - Thêm 2 đỉnh cho mỗi đoạn cong vì vậy mặt phẳng sẽ được biểu diễn bằng một đồ thị phẳng với các đoạn thẳng là D(G). - Thay mỗi cạnh của D(G) bằng một tập hợp các node thích hợp(gadget). Tâp hợp những điểm trong không gian 2 và 3 chiều là kết quả của sự thay thế này được gọi là S(G) Sau đây là các thuộc tính của một gadget: Cho một D(G) = (V, E) được xây dựng như phía trên. Cho λ, λ’ , ε ≥ 0 với điều kiện λ + ε > λ’ , và cho γ > 1. Với bất kỳ (a, b) ∈ E, gadget tương ứng là gab được tạo bởi sự phân chia tập hợp những điểm Vab= {a, b}, Yab= {yab, yba} Xab= {x1, . . . , xl1}, and Zab= {z1, . . . , zl2} l1, l2 phụ thuộc vào độ dài của (a,b). Tập hợp những điểm trong mặt phẳng R2 giữ những tính chất sau: (a) δ(a, yab) = δ(b, yba) = λ + ε. (b) Xab là một chuỗi những điểm vì vậy δ(a, x1) = δ(x1, x2) = … = δ(xl1 , b) = λ và, với bất kỳ i = j + 1, j − 1, δ(xi, xj) ≥ λ. (c) Zab là một chuỗi các điểm vì vậy δ(yab, z1) = δ(z1, z2) = … = δ(zl2, yba) = λ và , với bất kỳ i = j + 1, j − 1, δ(zi, zj) ≥ λ (d) Với bất kỳ xi∈ Xab, zj∈ Zab , δ(xi, zj) > λ + ε.Hơn nữa , Với bất kỳ i = 1, . . . , l1, δ(xi, yab) ≥ λ + ε và δ(xi, yba) ≥ λ + ε (e) Cho 2 gadget bất kỳ gab và gcd, với bất kỳ v ∈ gab\gcd và w ∈ gcd\gab,chúng ta có δ(v, w) ≥ λ. Hơn nữa, nếu v Vab∪ Xab hoặc w Vcd∪ Xcd thì δ(v, w) ≥ γ λ.. Trong Clementi et al. 1999 một giá trị thích hợp cho việc chọn λ, λ’, ε và γ trong khi thỏa mãn các điều kiện (a)…(e) thì một số tính chất sau cũng nên được thêm vào: (b’) δ(a, xj) > λ + ε với bất kỳ j 1, và δ(xi, b) > λ + ε với bất kỳ i l1. (c’) δ(yab, zj) > λ + ε với bất kỳ j1, và δ(zi, yba) > λ + ε với bất kỳ i l2 (d’) Với bất kỳ xi∈ Xab, zj∈ Zab, δ(xi, yab) > λ + ε, δ(xi, yba) > λ + ε, δ(zj, a) > λ + ε, và δ(zj, b) > λ + ε Cho những tính chất (a)…(e) và (b’)…(d’), nó chia mỗi gadget ra làm 2 thành phần có khoảng cách là λ + ε: thành phần VX bao gồm tập hợp những điểm trong Vab∪ Xab và thành phần YZ, bao gồm một dãy các điểm Yab∪ Zab.Hơn nữa , cho một cặp node bất kỳ (v, w) với v nằm trong VX và w nằm trong YZ , chúng ta có δ(v, w) = λ + ε khi và chỉ khi v = a w = yab hoặc v = b và w = yba. Gadget cho cạnh (a,b) được biểu diễn như trong hình bên dưới. Hình 7: Gadget cho cạnh (a, b) Chú ý rằng trong một vùng ảnh hưởng bất kỳ một node nào cũng phải có một transmitting range ít nhất là bằng với khoảng cách từ nó tới node hàng xóm gần nó nhất. Cho RAmin là range assignment cho S(G) như vậy mỗi node sẽ có transmitting range bằng khoảng cách từ nó đến hàng xóm gần nhất của nó. Cho một gadget với những thuộc tính như đã nêu ở phía trên và RAmin có nghĩa là những node trong VX sẽ có transmitting range là λ và những node trong YZ có transmitting range là λ’. Vì tính đối xứng của các điểm trong mặt phẳng nên RAmin là đối xứng. Đồ thị liên thông có RAmin được tạo bởi m+1 các thành phần kết nối, với m = |E|: trong VX có m kết nối và một kết nối với một gadget khác, vì vậy để có một đồ thị liên thông được kết nối và có tính đối xứng chúng ta cần định nghĩa một vài điểm cẩu nối (bridge points) giữa VX và YZ. Cho Y = Yab, X =Xab, Z = Zab, and V = Va,b. Dưới đây là những đinh nghĩa những tính chất của một range assignment đối xứng tối ưu (optimal symmetric range assignment) cho S(G). 3.4.3. (RA chính tắc) Một range assignment kết nối đối xứng cho S(G) được gọi là đối xứng nếu: RAc(v) = λ với bất kỳ v X; RAc(v) = λ’ với bất kỳ v Z RAc(v) = λ hoặc RAc(v) = λ + ε với bất kỳ v V RAc(v) = λ’ hoặc RAc(v) = λ + ε với bất kỳ v Y 3.4.4. Bổ đề (Blough et al. 2002) Cho S(G) là tập hợp các điểm nằm trong không gian R2 theo cách xây dựng được giới thiệu ở phía trên. γ, λ, và ε là các hằng số xác định sao cho: Thì với bất kì một range assignment kết nối đối xứng RA cho S(G) tồn tại một range assignment chính tắc RAc thỏa mãn c(RAc) ≤ c(RA). Chứng minh: Chúng ta sẽ chứng minh rằng với bất kỳ một range assignmet kết nối đối xứng không chính tắc RA nào đều có thể chuyển đổi thành assigment chính tắc RAc thông qua một chuỗi các bước lặp. Tại mỗi bước lặp sẽ không làm tăng thêm chi phí cho RA. Ở tất cả các bước cần chú ý rằng range assignment của node u là không chính tắc, qua các phép biến đổi chúng ta sẽ tìm ra một RA chính tắc cho u. Vì vậy số lượng những RA không chính tắc của từng node trong S(G) sẽ giảm dần theo từng bước lặp vì vậy những bước xử lý sẽ kết thúc trong một khoảng thời gian giới hạn. Sau đây chúng ta sẽ mô tả từng bước trong quá trình xử lý này: Cho v là một điểm không chính tắc và cho RA(v) là transmitting range của v, chúng ta có những trường hợp sau: 1. RA(v) < γ λ. Trong trường hợp này transmitting range của v không đủ rộng lớn để bao quát những node của thành phần YZ của một gadget khác. Chú ý rằng nếu RA(v) < λ + ε thì v không thể là bridge point giữa YZ và VX được, do vậy transmitting range có thể giảm λ hay λ’ (phụ thuộc vào v V X hay v Y Z) mà không phải cắt kết nối và duy trì tính đối xứng. Bây giờ chúng ta giả sử RA(v) ≥ λ + ε. Không mất tính tổng quát ta giả sử rằng v gab, với (a, b) E. Nếu v Vab Yab thì transmitting range của nó có thể được giảm đến λ + ε mà không phải ngắt kết nối và duy trì tính đối xứng. Nói cách khác, chú ý đến range assigment RAab như sau: RAab(w) = RA(w) với bất kỳ w S(G) − gab; RAab(a) = RAab(yab) = λ + ε; RAab(b) = λ và RAab(yab) = λ ; RAab(x) = λ với bất kỳ x Xab; RAab(z) = λ với bất kỳ z Zab. Cho thuộc tính của nhứng điểm trong một gadget như đã trình bày phía trên,thì ta có RAab là có tính đối xứng . Hơn nữa đồ thị liên thông thu được từ RAab đã được kết nối và RA là một range assingment chính tắc trong gab và vì vậy cho c(S(G)\gab) =∑vS(G)\g abRA(v)2. Để thỏa mãn yêu cầu về tính đối xứng nên ta có c(RA) ≥ c(S(G)\gab) + 2 * RA(v)2+ (l1+ 1) * λ2+ (l2+ 1) * λ’2 Với l1 = |Xab| và l2 = |Zab| Với một điều kiện khác nữa ta có c(RAab) = c(S(G)\gab) + 2 • (λ + ε)2+ (l1+ 1) • λ2+ (l2+ 1) • λ’2 Từ RA(v) ≥ λ + ε chúng ta có c(RA) − c(RAab) ≥ RA(v)2 − (λ + ε)2 ≥ 0 2. RA(v) ≥ γ λ trong trường hợp này v có thể là bridge point giữa nhiều YZ và VX. Không mất tính tổng quát ta giả sử rằng v gab, với (a, b) E . Chúng ta đầu tiên chuyển đổi range assignment như giới thiệu phía trên, thu được một range assignment RAab với c(RA) − c(RAab) ≥ γ2λ2− (λ + ε)2 . Tuy nhiên RAab nói chung là không đối xứng có thể có một vài YZ bị cô lập. Vì lý do này chúng ta chú ý rằng những thành phần bị cô lập YZ1, . . . , YZk trong đồ thị bởi RAab, và với mỗi thành phần này chúng ta cũng áp dụng cùng một phương pháp xây dựng như là xây dựng gadget gab . Và kết quả thu được là một range assignment là liên thông và đối xứng. Để chứng minh bổ đề trên chúng ta sẽ chứng minh c() ≤ c(RA). Chúng ta cần chú ý rằng chi phía để kết nối các thành phần YZi phải được công thêm vào range assignment mới . Tuy nhiên hãy để ý rằng vì tính đối xứng ít nhất một node trong YZi phải có transmitting range nhỏ hơn γ λ., cộng thêm cho mỗi YZ một giá trị là 2(λ + ε)2− (γ λ)2− λ2. Chú ý rằng k≤ m-1 và kết hợp với điều kiện ở bổ đề 4.4. chúng ta có kết luận: c(RA) − c() ≥ γ2λ2− (λ + ε)2− (m − 1)(2(λ + ε)2 − (γ λ)2− λ2) ≥ 0 Chúng ta kết thúc việc chứng minh ở đây Chú ý rằng đồ thị phẳng 2 chiều G và đồ thị trực giao của G là D(G) và cho 2h là số node được thêm vào trong bước thứ 2 của việc xây dựng. Gán cho mỗi node trong G và D(G) một ‘chi phí’ bằng với cấp bậc của nó. Bổ đề sau đây nêu lên mối quan hệ giữa chi phí của những đỉnh bao bọc bên ngoài của G với những đỉnh bọc bên ngoài của D(G). Bổ đề 4.4.5: đồ thị phẳng 2 chiều G và đồ thị trực giao của G là D(G) và cho 2h là số node được thêm vào trong bước thứ 2 của việc xây dựng Gán cho mỗi node trong G và D(G) một ‘chi phí’ bằng với cấp bậc của nó. Ta có chi phí của những node bao bọc của G ≤ k khi và chỉ khi chi phí của các cạnh bao bọc của D(G) ≤ k + 2h. Chứng minh: phần chứng minh của bổ đề này được trình bày trong Kirousis et al. 2000. Bây giờ chúng ta hãy xem xét tập hợp những điểm trong không gian 2 chiều S(G) thu được bằng cách xây dựng các gadget như đã được giới thiệu ở phần trên. Trong tài liệu Clementi et al. (1999) đã chứng minh rằng vơi bất kỳ một D(G) nào đều có thể suy ra được S(G) trong thời gian đa thức, và những điểm này nằm trong những gadget đều thỏa mãn những điều kiện (a)… (e), cho những hằng số xác định γ , λ, λ’ , ε với λ + ε > λ’ và Có thể nhận thấy rằng, chúng ta nên chọn cùng một giá trị cho λ, λ’ , ε cho các điểm trong các gadget, chúng ta sẽ có thêm các tính chất là (b’), (c’), (d’) Cho Y =a,bEYab, X =a,bEXab, Z =a,bEZab, và V=a,bEVab Chi phí của các đỉnh bao bọc C trong D(G) là k khi và chỉ khi S(G)có chi phí là (|X| + |V | − |C |) λ2+ (|Y | + |Z| − k))λ2+ (|C | + k) (λ + ε)2. Hãy chú ý rằng range assingment chính tắc RAc trên S(G) có các tính chất sau: RAc(v) = λ + ε với bất kỳ v C RAc(v) = λ với bất kỳ v V \C. Bây giờ hãy chú ý rằng với bất kỳ một range assignment kết nối đối xứng nào RA cho S(G), theo bổ đề 7.4.4 chúng ta có range assignment chính tắc RAc thì c(RAc) ≤ c(RA).Vì vậy chúng ta có thể giới hạn sự quan tâm của chúng ta vào range assignment chính tắc. Cho k là số lượng các điểm nằm trong Y có transmitting range là λ + ε, và C là tập hợp những điểm trong V có transmitting range là λ + ε. Chi phí của RAc là (|X| + |V | − |C |) λ2+ (|Y | + |Z| − k))λ’2+ (|C | + k) (λ + ε)2 . Vì RAc là chính tắc , điều này kéo theo C là các đỉnh bao bọc của D(G) và do tính đối xứng nên chi phí của C phải là k. Đây là điều phải chứng minh 3.2.Chi phí năng lượng của Range Assignment tối ưu. Trong phần trước chúng ta đã xem xét 2 vấn đề giới hạn của RA và chúng ta thấy rằng trong trường hợp mạng 2 và 3 chiều thì độ phức tạp tính toán của các vấn đề là không thay đổi với những trường hợp thông thường. Điều này cũng đồng nghĩa rằng chúng ta cần đánh giá những yêu cầu về chi phí năng lượng cho mọt Range tối ưu như thế nào để duy trì được các kết nối mạnh trong đó. Nói một cách khác, cRA, cWS và cS là chi phí cho RA , WSRA và SRA, như vậy đâu là mối quan hệ giữa các chi phí này. Rõ ràng răng cRA≤ cWS≤ cS Bằng nhiều thực nghiệm, người ta đã chứng minh được rằng cWS/cRA = O(1). Còn đối với cS/cRA chúng ta sẽ tìm hiểu xem mối quan hệ giữa chúng là như thế nào. Hình 8: Sự sắp xếp các node và khoảng cách giữa chúng Giả sử như trong mạng 1 chiều chúng ta có n node nằm trên 1 đường thẳng v1, . . . , vn(các node được sắp xếp từ phải sang trái) Khoảng cách giữa vi và vi+1 là d >0 với i = 1, . . . , n − 2 , và khoảng cách giữa vn-1 với vn là d*n.Bằng việc kết nối các node liên tiếp với nhau, chúng ta có RA và chi phí cho RA này là c(RA) = (n − 2)dα + 2(nd)α Nếu trong RA là yêu cầu về tính đối xứng thì RA(vn−1)≥ nd (điều này là cần thiết để kết nối node vn-1 với node vn) kéo theo với đó là node vi-1 có một liên kết vô hướng với tất cả các node vi với i = 1, n-2, điều này kéo theo RA(vi) ≥ nd với bất kỳ vi kéo theo cS≥ n(nd)α. từ đó chúng ta có cS/cRA = Ω(n). Nói cách khác những kết quả trên đây chứng minh rằng sự tiêu thu năng lượng trong các vấn đề là có các mối quan hệ với nhau. Và điều này sẽ được tính đến trong quá trình xây dựng các giao thức cho mạng ad-hoc. Chương 4. Hiệu quả năng lượng của sự kết nối các topology Trong phần trước, chúng ta đã xét đến vấn đề, đó là làm sao để tính toán tâp hợp những transmitting range với chi phí năng lượng là nhỏ nhất bằng cách tạo ra một đồ thị liên thông, Những nghiên cứu lớn được hầu hết dành cho là làm sao đồng nhất được những topologies để tạo ra hiệu quả trong việc sử dụng năng lượng cho các kết nối đối với mỗi node mạng. Hay nói một cách khác, chúng ta xác định một đồ thị liên thông G thu được khi tất cả các node đều truyền với tối đa sức mạnh, và mục đích là đồng nhất những đồ thị con G’ của G sao cho hiêu quả năng lượng được sử dụng để liên kết là tốt nhất mà vẫn giữ được những tính chất của G’. Tiêu chí xác định để đánh giá hiệu quả năng lượng trong một liện kết phụ thuộc vào kết nối mẫu đã được xác định từ trước. Thông thường 2 kiểu kết nối được chú ý đến đó là kết nối cuối cuối (end to end) giữa các node bất kỳ (hình thức này truyền là unicast) và kiểu kết nối 1 toàn bộ (one to all) (hình thức truyền là broadcast). Trong chương này, đầu tiên chúng ta sẽ phân tích vấn đề tối ưu hóa topology cho hình thức truyền unicast, và sau đó chúng ta sẽ xét vấn đề tương tự với hình thức truyền là broadcast. Chú ý rằng tất cả những kết quả thu được trong chương này đều dành cho mạng 2 chiều 4.1. Hiêu quả năng lượng Unicast Cho G(N, E) là một đồ thị với sức mạnh tối đa (maxpower graph) có nghĩa là một một đồ thị liên thông được tạo ra khi tất cả các node khi các node kết nối và đều truyền với tối đa sức mạnh. Trong đồ thị trên chúng ta giả sử G là đã được kết nối. Cho Puv là một đường kết nối có hướng giữa node u và node v trong G. Chi phí (power cost ) Puv = {u = w0, w1, . . . , wh, wh+1=v} được định nghĩa như là tổng chi phí của các cạnh đơn, đó là : pc(Puv) =δ(wi, wi+1)α. Với α là hệ số suy giảm năng lượng theo khoảng cách. Đường kết nối giữa node u, v trong G và bị giới hạn bởi điều kiện là khoảng cách nhỏ nhất (tương ứng với minimum power) được xác định là được gọi là minimum power path giữa node u và v trong G. Nếu minimum power path giữa u và v là không đơn nhất, chúng ta chọn bất kỳ một con đường nào đó và nó sẽ được đánh giá như là một minimum power path. 4.1.1 (Hệ sỗ dãn power): Cho G’ là một đồ thị con tùy ý của đồ thị G như đã cho ở trên. Hệ số dãn power của G’ liên quan tới G được xác định theo công thức sau: Quy định rằng chúng ta định nghĩa ρG= ∞ nếu giữa node u và v tồn tại kết nối trong G và không có kết nối ở G’. Hệ số dãn power là một sự suy rộng của khái niệm hệ số co dãn khoảng cách (distance stretch factor ), khái niệm của nó được nêu trong tài liệu Goodman and O’Rourke 1997. Đôi khi hệ số này còn được gọi là hệ số bước nhảy (hop stretch factor). Một ví dụ về maxpower graph G và đồ thị con G’ với các hệ số power stretch, distance stretch, hop stretch. . Hình 9: Đồ thị maxpower G và đồ thị con G’ với các hệ số power stretch 4.1.2 (Power spanner): Cho G(N, E) là một đồ thị với sức mạnh tối đa (maxpower graph) với |N|=n. Một đồ thị con G’ của G được gọi là Power spanner nếu ρG = O(1). Nói chung, chúng ta sẽ tìm kiếm một đồ thị con G’ (còn gọi là đồ thị định tuyến) của đồ thị G, và đồ thị con này có hệ số power stretch thấp và điều này khá là quan trọng so với đồ thị ban đầu. Đồ thị định tuyến này có thể được coi như là đầu vào của giao thức định tuyến và nó sẽ tính toán những đường đi giữa các node chỉ trong đồ thị G’ mà ta đang xét. Cho những tính chất của power spanning, chúng ta có thể đảm bảo rằng năng lượng dùng cho việc kết nối với những tuyến đường là “gần như tối thiểu”. Lợi ích của việc sử dụng G’ thay G đó là routing overhead được giảm. Hãy chú ý rằng trong phương pháp tiếp cận này vấn đề kiểm soát topology hoàn toàn được giả định rằng từng node có thể thay đổi năng lượng truyền trên từng gói tin cơ bản: khi một node u gửi một gói tin tới node v, nó sẽ thiết lập một cấp độ năng lượng để truyền có giá trị tối thiểu cần thiết để đạt tới node kế tiếp trong quãng đường định tuyến tới v. Bên cạnh đó là một sparse power spanner (đồ thị trên n node được gọi là sparse nếu số lượng cạnh trong đồ thị này là O(n), và một vài tính chất mong muốn của đồ thị định tuyến cũng được xác định. Đi vào chi tiết, bậc của những node trong topology được xây dựng bị ràng buộc bởi một hằng số. Hãy chú ý thực tế là bậc của những node trong G’ được đảm bảo là một giá trị trung bình , không phải là lớn nhất, bậc của những node trong đồ thị là một hằng số. Sở dĩ có rằng buộc này nhằm mong muốn tránh hiện tượng ‘nút cổ chai’ (bottle necks) trong trong đồ thị liên thông. Nếu đồ thị định tuyến được sử dụng cùng với các giao thức định tuyến thì tính 2 chiều được đảm bảo trong việc chuyển các bản tin. Cuối cùng và quan trọng nhất là, đồ thị định tuyến phải được xây dựng trong một khu vực hạn chế và được sự phân bố các node là hoàn toàn tùy ý. Hay nói cách khác bất kỳ một node u nào trong mạng đều có thể tính toán vị trí của nó trong G’ dựa trên cơ sở những node hàng xóm gần nó nhất trong đồ thị cha của nó là G. Tổng kết lại rằng, đồ thị định tuyến G’ nên: Là một power spanner của đồ thị maxpower Là một sparse Có giới hạn về bậc của node Có tính 2 chiều Dễ dàng cho việc tính toán trong việc phân bố và xắp xếp các vị trí của node. Một số đồ thị định tuyến đáp ứng được một vài hoặc toàn bộ các yêu cầu trên được nói trong tài liệu. Hầu hết các đồ thị này đều dựa trên cơ sở đồ thị con của G. Trong thực tế, có thể dễ dàng nhận thấy là nếu một đồ thị định hướng G’ nào đó là distance spanner của đồ thị G thì nó cũng là power spanner của đồ thị G (chú ý là nếu đảo ngược lại nghĩa là G’ là power spanner của G thì nó chưa chắc là distance spanner của G). Vì vậy hầu hết các nghiên cứu dành cho distance spanner trong việc tính toán hình học để sử dụng để thiết kế một đồ thị định tuyến tốt. Hình 10: Bảng các đồ thị định tuyến và các hệ số liên quan Đi vào chi tiết , những đồ thị sau đây thu được từ việc tính toán hình học được sử dụng để xây dựng đồ thị định tuyến cho mạng ad-hoc: Relative Neighborhood Graph (RNG), Gabriel Graph (GG), Delaunay Triangulation (DT), và Yao Graph với tham số c (YGc).Những đồ thị này được gọi là proximity graphs.Từ việc thiết lập các kết nối liên quan tới một node bất kỳ u của đồ thị được tạo ra có thể được tính toán dựa trên cơ sở là vị trí của các node hàng xóm trong đồ thị maxpower. Vì vậy những proximity graph có thể được xây dựng trong một vùng giới hạn và các node là phân bố tùy ý. Sau đây là các mối quan hệ giữa các promixity graph đã được chứng minh: cho một tập hợp các điểm N RNG(N ) GG(N ), và RNG(N ) YGc(N ), với c ≥ 6. Hơn nữa MST(N ) bao gồm RNG(N ), GG(N ), DT(N ), và YGc(N ), với c ≥ 6. Tỉ lệ distance và power spainning của những đồ thị trên được tổng kết trong bảng phía trên cùng với bậc trung bình và lớn nhất của những node.Trong bảng trên RDT được giới hạn bởi Delaunay Triangulation (những cạnh vượt quá transmitting range của node sẽ bị loại bỏ). Như nhìn trong bảng, GG có hệ số power stretch là tối ưu.Thuật toán đươc trình bày bên dưới có thể được sử dụng để tính toán GG trong một vùng giới hạn và có sự các cách phân bố tùy ý các node.Thuật toán này dựa trên giả thiết là tất cả các node trong mạng đều biết vị trí của nó trong mặt phẳng, điều này hoàn toàn có thể thực hiện bằng công nghệ GPS hoặc là một số công nghệ tìm kiếm vị trí khác. Chúng ta nhắc lại rằng một cạnh (u, v) G là được nằm trong đồ thị Gabriel khi và chỉ khi đường tròn với đường kính là cạnh (u, v) không bao gồm các node của G (Hình bên dưới): Hình 11: Một vùng bao phủ của 1 node trong đồ thị Gabriel Điều này có thể ngay lập tức được nhìn thấy trong thuật toán đươc trình bày ở bên dưới. Cần chú ý rằng bậc lớn nhất của node trong trong đồ thị maxpower có thể cao như là n-1.Có thể dễ dàng nhận thấy rằng thuật toán có độ phức tạp thời gian là O(n2). Độ phức tạp thông báo là O(n) khi tất cả các node trong đồ thị đều truyền với thông báo đơn. Mặc dù GG có hệ số power stretch là tối ưu, nhưng bậc của node có thể tăng lên đến n-1.Những giá trị của các đồ thị khác cũng được liệt kê trong hình 10. Vì lý do này một số biến thể của proximity graphs đã được đề xuất với mục đích có một ràng buộc trên bậc lớn nhất của node. Thật không may mắn rằng vấn đề này đã được đem ra nghiên cứu và không có một đồ thị nào có bậc của node là hằng số mà vẫn thỏa mãn được điều kiện là có 1 đường đi với minimum power cho bất kỳ một cặp node nào. Chính vì vậy mà không có một power spainner tối ưu nào với một hằng số được giới hạn bởi bậc tối của node tồn tại. Ngày nay đồ thị định tuyến với bậc node là hằng số có hệ số power stretch tố nhất là đồ thị OrdYaoGG.Nó được tạo bởi xây dựng đồ thị YGc với c ≥ 6. trên đồ thị GG. Đồ thị OrdYaoGG có hệ số power stretch là và bậc lớn nhất của node c+5 với c> 6 là tham số của đồ thị Yao. Ví dụ cho c = 9 và α = 2 chúng ta có hệ số power stretch là 1.88 và giới hạn bậc tối đa của node là 14.Mặc dù OrdYaoGG có thể được xây dựng trong một vùng giới hạn và các node được phân bố tùy ý, nhưng yêu cầu tính toán của nó một số lượng nhất định các bản tin trao đổi. (24n bản tin là ít nhất) Vì lý do này những tác giả đã đề xuất đồ thị SyaoGG nó cũng tương tự như đồ thị OrdYaoGG nhưng số bản tin tối thiểu yêu cầu trao đổi là 3n. Hệ số power stretch là và bậc lớn nhất là c. với c >8 là tham số của đồ thị Yao. Ví dụ cho c = 9, α = 2 chúng ta có hệ số power stretch là 31.11 và bậc tối đa của node là 9. Thuật toán Gabriel Graph (Thuật toán cho sự xây dựng đồ thị Gabriel Graph) IDu là định danh của node u, (xu, yu) là vị trí của node u EG(u) và EGG(u) là tập hợp những liên kết của u trong đồ thị maxpower và của GG. Disk(u,v) là môt đường tròn với cạnh (u, v) là đường kính. 1, Khởi tạo EG(u) = EGG(u) = Φ. 2. Xử lý khi một bản tin đến - Trong khi nhận bản tin (IDv,(xu,yu)) từ node v add thêm (u, v) vào EG(u). - Kiểm tra xem cạnh (u, w) có thực sự thuộc EG(u) như là w disk(u, v). - Nếu không thêm (u, v) vào EGG(u) - Với mỗi (u, w) EGG(u): + Kiểm tra xem v disk (u, w). + Nếu có thì xóa (u, w) trong EGG(u). 3. Kết thúc Sau khi xử lý xong tất cả các bản tin đến, EGG(u) sẽ bao gồm tất cả các cạnh của GG liên quan tới u. 4.2. Hiệu quả năng lượng broadcast Một vấn đề khác được xem xét trong tài liệu này đó là việc xác định những topology cho sự hiệu quả năng lượng của broadcast: chúng ta cho một đồ thị maxpower G, mục đích là xác định những đồ thị con G’ của G (đồ thị broadcast) như là sự quảng bá trong G’ trong đó hiệu quả năng lượng được sử dụng cho đồ thị này như là trong đồ thị maxpower. Điểm lợi của việc sử dụng những đồ thị này thì các vấn đề ta xem xet sẽ “nhỏ hơn” so với đồ thị maxpower như là hiện tượng nhiễu trong chế đồ truyền broadcast có thể sẽ được giảm. Hiện tượng này xảy ra khi những node trong những vùng lân cận cố gắng truyền lại những bản tin broadcast trong cùng một thời điểm, kết quả là gây ra một sự dư thừa lớn, cạnh tranh băng thông và xung đột. Trước khi trình bày những kết quả chúng ta sẽ giới thiệu một khái niệm hệ số broadcast stretch. Bây giờ chúng ta hãy xem xet đồ thị maxpower G. Bất kỳ quảng bá nào được tạo ra bởi node u có thể được xem như là một cây có hướng của đồ thị G với root là node u, chúng ta gọi nó là cây broadcast (broadcast tree). Chi phí năng lượng của cây broadcast T được định nghĩa như sau. Gọi pcT(v) là chi phí năng lượng phải trả khi truyền bản tin broadcast tại node v, pcT(v) = 0 nếu v là node lá của cây T và pcT(v) = max(v,w) δ(v, w)α nếu khác. Tổng năng lượng cần để truyền bản tin broadcast trong cây T là pc(T) = ∑(v∈N)pcT(v). Chúng ta gọi chi phí này là chi phí năng lượng của T (power cost T). Cây được tạo ra bởi G với root là u với chi phí năng lượng nhỏ nhất được gọi là minimum power broadcast tree của u và được ký hiệu là Tumin,G. Định nghĩa 4.2.1 (Hệ số broadcast stretch) Cho G’ là một đồ thị con tùy ý của đồ thị maxpower G (N,E), hệ số power stretch của G’ đối với G được gọi là βG là giá trị lớn nhất giữa tỉ lệ chi phí năng lượng nhỏ nhất của cây broadcast của G’ với root là u và chi phí năng lượng nhỏ nhất của cây broadcast của G với root là u. βG’ = Định nghĩa 4.2.2 (Broadcast spanner) Cho G(N, E) là đồ thị maxpower với |N| = n. Một đồ thị con G’ của G được gọi là broadcast spanner của G nếu βG O(1) Tương tự như trường hợp của unicast mục đích của chúng ta là tìm những broadcast spanner rời rạc của G điều này có thể được tính toán trong một khu vực được gới hạn và phân bố tùy ý. Không may mắn rằng nhiệm vụ được đưa ra này khó khăn hơn nhiều so với trường hợp unicast.Khó khăn chính xảy ra đến từ sự thật là việc tính toán chi phí năng lượng nhỏ nhất cho cây broadcast tree có root ở một node là một vấn đề NP-hard, dưới giả thiết là các node có thể sử dụng một bộ các cấp độ năng lượng rời rạc {P1, . . . , Pk}. Vì vậy việc trực tiếp tính toán hệ số power stretch của đồ thị con G’của G là gần như không thể thực hiện được, từ điều này yêu cầu một hướng giải quyết cho vấn đề NP-hard. Căn cứ vào kết quả hardness, một số nhà nghiên cứu đã đề xuất một số giải pháp, những đề xuất này là giải pháp cho vấn đề tố ưu chi phí nhỏ nhất của cây broadcast theo một giá trị gần đúng. Một trong những nghiên cứu này sẽ được chúng ta đề cập tới đây là thuật toán Broadcast Incremental Power (BIP).Thuật toán BIP được trình bày trong bên dưới.Thuật toán này là một biến thể của thuật toán Prim cho việc tìm kiếm MST.Thuật toán bắt đầu bằng việc tìm kiếm một node nguồn u để có thể đạt tới mức chi phí nhỏ nhất. Node này sẽ được thêm vào tập hợp những node covered C, đó là những node có thể nhận bản tin broadcast. Một điểm chung ở bước thứ i, BIP xét tất cả những node chưa nhận nhận bản tin broadcast và với bất kỳ node v nào tín toán chi phí được tăng lên của việc thêm node v vào spanning tree hiện thời.Node v với chi phí tăng lên tối thiểu sẽ được thêm vào tập hợp C và là một phần của spanning tree hiện thời. Xử lý này được lặp lại cho đến khi tất cả các node là covered. Một broadcast spanner của G có thể đươc xây dựng như sau: cho một node bất kỳ u trong G, áp dụng thuật toán BIP để xây dựng cây broadcast Tu với root của cây là u. Cho GBIP = Uu N Tu , nghĩa là, liên kết (u,v) là trong GBIP khi và chỉ khi nó được nằm trong cây broadcast được tính toán bởi BIP. Cho phương pháp BIP là phương pháp xấp xỉ tối ưu (được xây dựng trên đồ thị maxpower) với hệ số lớn nhất là 12, sau đây ta có: với bất kỳ một node u, GBIP bao gồm 1 cây broadcast với root là u và chi phí của nó gấp O(1) lần so với chi phí của cây tối ưu, nghĩa là GBIP là một broadcast spanner của G. Không may mắn rằng là đồ thị GBIP là khá nhiều.Hơn nữa BIP là một thuật toán tập trung, và yêu cầu là phải biết tất cả các node. Một đồ thị khác có thể được sử dụng để xây dựng broadcast spanner là MST, nó xấp xỉ cây broadcast với chi phí nhỏ nhất bằng hệ số giữa 6 và 12. Không may rằng việc tính toán của MST cũng yêu cầu phải biết tất cả các node.Để giải quyết vấn đề thì người ta thường đưa ra một điều kiện là thuật toán chỉ nên được triển khai trong một vùng hạn chế. Tóm lại, việc thiết kế một thuật toán đươc giới hạn trong một phạm vi và được phân phối tùy ý có thể được sử dụng để xây dựng một broadcast spanner của G đang còn là một công việc khác phức tạp. Thuật toán BIP u là node nguồn C là tập hợp những node đã được xét T là spanning tree N là tập hợp những node mạng 1. Khởi tạo C = {u} T = {u} 2 Lặp cho đến khi C = N với mỗi node v N – C Tính toán chi phí tăng thêm ic(v) khi thêm c vào T Cho trong N-C với chi phí tăng thêm nhỏ nhất C = C {} Thêm vào spanning tree hiện thời T 3 Kết thúc Khi C = N, T là cây broadcast spanning với gốc là u. Trước khi kết thúc chương này chúng ta sẽ điểm lại một số nét chung giữa vấn đề range assignment được trình bày trong chương 3 và vấn đề hiệu quả năng lượng trong chế độ broadcast. Giả sử có G là một đồ thị maxpower trên tập hợp N điểm, trong vấn đề RA mục đích của chúng ta là tìm ra một range assigment với chi phí tối ưu khi đồ thị này có kết nối. Giả sử ta có một node u tùy ý muốn quảng bá bản tin m, và cho RA là một range assignment tối ưu, một sơ đồ quảng bá đơn giản là lan truyền: node u truyền m ở một khoảng cách là RA(u), và mỗi node khác là v nhận được m trong khoảng thời gian đầu tiên, sau đó nó sẽ truyền lại m theo một khoảng cách là RA(v), ngay lập tức chúng ta thấy rằng sau đó tất cả các node N sẽ được truyền một bản tin m, sự quảng bá đã được lan truyền khắp trong mạng. Vì vậy chi phí năng lượng cho RA là một giới hạn của chi phí năng lượng của bất kỳ cây broadcast nào trong G. Chương 5. Mô phỏng và kết quả thực nghiệm 5.1. Ý tưởng xây dựng một chương trình mô phỏng Mạng ad-hoc được xây dựng từ ý tưởng đó là giả sử coi các node trong mạng là những cảm biến, các cảm biến sẽ tạo nên một mạng ad-hoc, hay là một mạng cảm biến. Xây dựng nên một mạng ad-hoc với sự thay đổi số lượng các node (các cảm biến) tham gia Xây dựng nên một RA tối ưu với thuật toán MST, Prim Giả lập có sự truyền tải gói tin giữa các node Tính toán sự tiêu thụ năng lượng So sánh sự tiêu thụ năng lượng giữa khi mạng có một RA tối ưu và khi không có RA tối ưu. Từ đó đưa ra đánh giá về mức độ ảnh hưởng của RA đến sự tiêu thụ năng lượng. 5.2. Xây dựng chương trình mô phỏng Chương trình được xây dựng theo nhiều module và gép nối các module với nhau để mô tả những ý tưởng đã được nêu trên. Sau khi gép nối các module với nhau, chương trình sẽ có khả năng mô phỏng mang ad-hoc một cách cơ bản. Giao diện chính của chương trình được trình bày trong hình bên dưới. Hình 12: Giao diện chính của chương trình Module chính của chương trình là Wireless Sensor NetWork đảm nhiệm vai trò: Xây dựng một mạng ad-hoc với các thông số cơ bản của các node Xây dựng các hàm có chức năng mô phỏng mạng Xây dựng một RA tối ưu bằng MST a) Xây dựng một mạng ad-hoc với các thông số cơ bản của node: public WirelessSensorNetwork(variables): hàm này cho phép khởi tạo các thông số cơ bản của một mạng ad-hoc như: số lượng các node, năng lượng dành cho mỗi node, tọa độ, vùng giới hạn của mang … b) Xây dựng các hàm có chức năng mô phỏng mạng ad-hoc public void BuildNetwork(bool bOptimizeRA): cho phép xây dưng mang ad-hoc với các thông số được khởi tạo như trên, nếu là RA tối ưu thì xây dựng theo RA tối ưu. public bool Process(): hàm xử lý toàn bộ các trao đổi trong mạng ad-hoc, tính toán các giá trị năng lượng cập nhật cho các biến … c) Xây dưng RA tối ưu bằng MST internal bool OptimizeRA(): hàm xây dựng RA tối ưu dựa vào thuật toán Prim, MST 5.3. Kết quả mô phỏng Dựa vào chương trình mô phỏng chúng ta có bảng thông số nhứng kết quả sau đây Số lượng các node Năng lượng cung cấp Thời gian tồn tại của mạng khi RA là tối ưu Thời gian tồn tại của mạng khi RA không tối ưu Số lượng gói tin giao tiếp trong mạng khi RA là tối ưu Số lượng gói tin giao tiếp trong mạng khi RA là không tối ưu 10 10000 2.34 1.40 328 307 50 50000 2.47 209 456 427 100 100000 1.44 1.32 788 746 130 130000 2.14 1.46 868 859 5.4. Nhận xét Dựa vào kết quả của chương trình mô phỏng, chúng ta có thể nhận thấy rằng với RA tối ưu thì khả năng giao tiếp của mạng được nâng lên, số lượng các gói tin giao tiếp trong mạng được tăng lên, đồng thời giảm thiểu được năng lượng sử dụng cho các node trong mạng. Nâng thời gian tồn tại của mạng tăng lên. Chương 6. Kết luận 6.1. Những kết quả đạt được và mặt hạn chế của khóa luận Nghiên cứu về lĩnh vực truyền thông của mạng ad-hoc là một lĩnh vực tương đối khó và là một trong những vấn đề mới của truyền thông không dây nói chung. Nó yêu cầu người nghiên cứu phải có kiến thức sâu rộng không những về mạng nói chung mà còn đòi hỏi người nghiên cứu phải có những tính toán tỉ mỉ, khả năng ước lượng cao kiên trì và chi tiết vì mạng không dây nói chung bị ảnh hưởng bởi rất nhiều yếu tố khác nhau. Mặc dù kiến thức, kinh nghiệm còn non kém song trong quá trình làm khóa luận em đã đạt được một số kết quả đáng chú ý sau: Nghiên cứu được các lý thuyết về sự mô hình hóa mạng ad-hoc Tính toán và tìm được những giải pháp cho việc tối ưu hóa vùng ảnh hưởng cho từng node trong mạng ad-hoc Chứng minh được với một vùng ảnh hưởng là tối ưu sẽ tiết kiệm được năng lượng sử dụng cho từng node nói riêng và toàn mạng ad-hoc nói chung Thiết kế được chương trình mô phỏng một mạng ad-hoc đơn giản Lập trình và tìm ra được những vùng ảnh hưởng là tối ưu cho từng node trong mạng ad-hoc theo thuật toán Prim và MST Mô phỏng được quá trình truyền dữ liệu giữa các node và tính toán được năng lượng tiêu thụ cho mạng ad-hoc Do giới hạn về mặt kiến thức, thời gian và non kém về kinh nghiệm nên khóa luận của em còn có những mặt hạn chế nhất định: Những sự chứng minh các công thức và các vấn đề liên quan đến việc mô phỏng còn chưa được nêu ra toàn bộ Do là mạng mô phỏng nên nhiều đặc tính của node cũng như ảnh hưởng của môi trường là do người thiết kế tự đưa ra, có thể còn chưa sát với thực tế Chương trình mới dừng lại ở mức độ trung bình sự di chuyển và biến đổi của các node là chưa cao Vùng ảnh hưởng tối ưu đưa ra chỉ mang tính chất tương đối, có thể chưa đưa ra được một vùng ảnh hưởng tối ưu nhất giúp phần tiết kiệm năng lượng một cách tối ưu nhất 6.2. Phương hướng phát triển Nghiên cứu các lý thuyết toán học sao cho tìm được một vùng ảnh hưởng và tìm kiếm được những topology là tối ưu nhất Xây dựng chương trình mô phỏng một cách chính xác và sát với thực tế hơn Tài liệu tham khảo [1]. David J. Stein, “Wireless Sensor Network Simulator” [2]. Paolo Santi, “Topology Control In Wireless Ad hoc and Sensor Networks”, trang 1-9.. [3]. Paolo Santi, “Topology Control In Wireless Ad hoc and Sensor Networks”, trang 13-25. [4]. Paolo Santi, “Topology Control In Wireless Ad hoc and Sensor Networks”, trang 73-85 [5]. Paolo Santi, Topology Control In Wireless Ad hoc and Sensor Networks, trang 87-92.