Luận văn Bảo đảm công bằng luồng trong các mạng ad hoc không dây

ưu lượng dữ liệu chuyển tiếp Để làm giảm bớt sự khơng cơng bằng, một cách khác cho phép gán các 49 trọng số khác nhau tới mỗi hàng đợi để hàng đợi với lưu lượng dữ liệu chuyển tiếp sẽ nhận nhiều băng thơng hơn khi cần thiết. Sự phối hợp này là mơ hình như trình bày trong hình 2.5(c), ở đĩ hình đĩa lớn hơn biểu thị rằng một trọng số lớn hơn cho hàng đợi đang chuyển tiếp. Trọng số hàng đợi đang chuyển tiếp cĩ thể được cố định trong tất cả các nút của mạng, hoặc các trọng số khác nhau cĩ thể được sử dụng, phụ thuộc vào số lượng lưu lượng dữ liệu chuyển tiếp tại mỗi nút. Cuối cùng giả thiết rằng số lượng lưu lượng dữ liệu chuyển tiếp cĩ thể bằng cách nào đĩ được xác định theo một cách phân phối. Đối với mạng được trình bày trong hình 2.4, các tỷ lệ trọng số mong muốn của gốc đối lập với lưu lượng dữ liệu chuyển tiếp tương ứng là 1:3 và 1:1 cho nút 1 và 2. Như trong trường hợp mục trước, tỷ lệ thơng lượng tầng mạng bằng 1:1:1:1 và tỷ lệ thơng lượng tầng MAC tương ứng bằng 4:2:1:1 cĩ thể được duy trì khi tốc độ đưa ra tại mỗi nút ít hơn G. Khi mạng bão hồ, các thơng lượng cho mỗi luồng hội tụ tương ứng tới N B 4 , N B 16 3 , N B 8 3 và N B 16 3 . Kết quả tỷ lệ thơng lượng cho mỗi luồng của các nút 1-4 là 4:6:3:3 và tỷ lệ thơng lượng tầng MAC tương ứng là 1:1:1:1. Cho nhiều trọng số với lưu lượng dữ liệu chuyển tiếp hơn nữa làm giảm bớt vấn đề khơng cơng bằng, và tuy nhiên nĩ khơng đạt được sự cơng bằng lý tưởng. Sự khơng cơng bằng hiện nay là kết quả của cấu trúc liên kết khơng đối xứng của mạng, điều này thường là trường hợp trong một mạng thực. Tại nút 1, các gĩi tin đến từ nút 2 và 3 là được xử lý như nhau, mặc dù nút 2 phải chia sẻ băng thơng với nút 4. 2.2.2.3. Hàng đợi cho mỗi luồng Một phương pháp phổ biến hơn là sử dụng hàng đợi cho mỗi luồng. Như trình bày trong hình 2.5(d), các gĩi tin của các luồng khác nhau được xếp vào hàng riêng biệt (dựa trên địa chỉ nguồn tầng mạng của chúng). Các luồng đơn hướng về phía gateway được xem xét trong lúc này. Khi mạng bão hồ, thơng lượng Fi của luồng ith là: 4 1  N BF i 50 Tại nơi đĩ cĩ thể tồn tại những mạng đang thiếu tài nguyên để làm hàng đợi cho mỗi luồng (chẳng hạn, trong một mạng cảm biến lớn). Tuy nhiên, trong nhiều ứng dụng đặc biệt là trong việc truy cập mạng ở đĩ nhiều ứng dụng đa chặng xảy ra đụng độ, hàng đợi cho mỗi luồng là một sự phối hợp khả thi. 2.2.3. Cơ chế phối hợp điều khiển truyền Cơ chế phối hợp điều khiển truyền [9] đã đề xuất một cơ chế theo đĩ tầng MAC theo dõi việc mất các gĩi tin trong mơi trường khơng dây và điều khiển tốc độ lưu lượng. Cơ chế này tập trung xem xét cách điều khiển truy cập mơi trường trong mạng cảm biến được thực hiện theo nhiều cách khác nhau. Đầu tiên, nghiên cứu cách thức để cơ chế nghe thích hợp với trường hợp ở đĩ tất cả các nút cĩ thể nghe được nhau. Tiếp theo, cách mà backoff nên được bổ sung trong một mạng cảm biến và cuối cùng là cơ chế trong mạng đa chặng (bao gồm cơ chế điều khiển tranh chấp RTS/CTS truyền thống, cơ chế điều khiển tốc độ và cơ chế điều khiển tránh các nút ẩn trong mạng đa chặng). Tuy nhiên, cơ chế này chỉ tập trung trong trường hợp nơi đĩ sự khơng cơng bằng cho mỗi luồng được gây ra chủ yếu bởi tầng liên kết. 2.2.3.1. Cơ chế nghe Cơ chế đa truy nhập cảm nhận sĩng mang (CSMA) và phát hiện xung đột (CD) được tìm thấy trong mạng Ethernet là một ví dụ của cơ chế nghe. Nghe rất hiệu quả khi tất cả các node cĩ thể nghe được lẫn nhau (nghĩa là khơng cĩ các nút ẩn). Thật khơng may, sự phát hiện xung đột là khơng thể thực hiện được trong cơng nghệ mạng khơng dây nếu khơng cĩ sơ đồ mạch bổ sung. Mặc dù nghe là đơn giản, nĩ làm xuất hiện chi phí năng lượng, bởi vì sĩng vơ tuyến phải được bật để nghe. Để giữ gìn năng lượng, điều quan trọng là rút ngắn chiều dài cảm nhận sĩng mang. Nhiều giao thức như IEEE 802.11 yêu cầu cảm nhận kênh thậm chí trong suốt quá trình backoff. Tuy nhiên, CSMA cho các mạng cảm biến nên lấy cơ hội này để tắt sĩng vơ tuyến. Bản chất đồng bộ cao của lưu lượng dữ liệu áp đặt một tiêu chuẩn mới cho CSMA. Do khơng cĩ cơ chế phần cứng để phát hiện xung đột, các node mà xảy ra việc gửi tại cùng thời điểm sẽ gây lỗi lẫn nhau. Nếu mơ hình lưu lượng dữ liệu của mỗi nút là độc lập, tình trạng này sẽ khơng cĩ khả năng lặp 51 lại. Tuy nhiên, sự phát hiện một sự kiện vật lý chung sẽ đồng bộ hĩa các nút này và dẫn đến chúng gửi tại cùng một thời điểm, điều này sẽ lặp lại một cách định kỳ. Kết quả là khơng phải truyền tất cả gĩi tin. Giải pháp đưa ra độ trễ ngẫu nhiên cho quá trình truyền để khơng đồng bộ hĩa các node. 2.2.3.2. Cơ chế backoff Backoff là cơ chế được sử dụng rộng rãi trong điều khiển truy nhập mơi trường để giảm tranh chấp. Ý tưởng của backoff là để hạn chế một node truy cập từ kênh trong một chu kỳ thời gian và hy vọng rằng, kênh sẽ trở nên rỗi sau chu kỳ backoff. Trong trường hợp các mạng cảm biến ở đĩ lưu lượng dữ liệu là một sự xếp chồng của các luồng chu kỳ khác nhau, backoff sẽ khơng chỉ hạn chế một node đang gửi trong một chu kỳ backoff. Trong thực tế, chu kỳ backoff sẽ được áp dụng khi một pha dịch chuyển đến một chu kỳ ứng dụng do đĩ sự đồng bộ giữa chu kỳ các luồng lưu lượng dữ liệu cĩ thể bị phá vỡ. 2.2.3.3. Cơ chế tranh chấp cơ sở Rõ ràng các cơ chế điều khiển tranh chấp, được dùng rộng rãi trong nhiều giao thức MAC (ví dụ, IEEE 802.11 và MACAW), yêu cầu sử dụng các gĩi tin điều khiển, như yêu cầu gửi (RTS) và sẵn sàng để nhận (CTS). Các xác nhận (ACK) phục vụ một mục đích khác trong IEEE 802.11, chúng chỉ ra khơng cĩ xung đột. Trong các mạng máy tính nơi mà các gĩi tin cĩ kích thước lớn, những gĩi tin điều khiển nhỏ này được áp đặt rất ít chi phí. Tuy nhiên, trong các mạng cảm biến nơi mà kích thước gĩi tin nhỏ, chúng cĩ thể thiết lập một chi phí lớn. Một chuỗi giao thức bắt tay RTS - CTS - DATA -ACK trong quá trình truyền một gĩi tin cĩ thể thiết lập một chi phí tăng lên đến 40% (mỗi một gĩi tin điều khiển cĩ độ dài 3 byte (kiểu, đích, nguồn) và gĩi tin cĩ độ dài 30 byte). Điều này cĩ thể cực kỳ quý giá, vì năng lượng đã được dùng hết trong CSMA, quá trình truyền, và nhận mỗi gĩi tin điều khiển. Một lợi ích của mạng đa chặng hai chiều đĩ là các xác nhận độc lập khi một node nhận đang (phần tử cha trong cấu trúc liên kết đa chặng) định tuyến gĩi tin tới phần tử cha của nĩ. Điều này rõ ràng loại trừ một gĩi tin điều khiển ACK. Nếu nguồn nhận thực hiện một số loại ứng dụng đặc trưng trước khi kết hợp định tuyến gĩi tin, 52 nguồn khởi tạo của gĩi tin cĩ thể vẫn cĩ khả năng phát hiện sự thành cơng của quá trình truyền. Một cơ chế điều khiển tranh chấp cho các mạng cảm biến sẽ sử dụng số lượng nhỏ nhất các gĩi tin điều khiển. Các kiểu cơ bản nhất là RTS và CTS. Tuy nhiên nĩ cĩ thể hiệu quả trong việc giải quyết vấn đề nút ẩn trong một mạng đa chặng, như vậy một cơ chế sẽ chỉ được sử dụng nếu tổng số lưu lượng dữ liệu cao hơn trong khi một cơ chế CSMA đơn giản sẽ thực sự phù hợp đối với lưu lượng dữ liệu thấp khi xác xuất của sự sai lạc do xung đột là rất nhỏ. Với cơ chế tranh chấp này, chỉ các gĩi tin RTS và CTS được sử dụng mục đích là bắt tay. Một node mong muốn truyền đầu tiên để gửi một gĩi tin RTS tới phần tử cha của nĩ và chờ cho đến khi một CTS trả lời. Nếu khơng cĩ CTS nào nhận được trong một quãng thời gian chờ đợi (2 lần gĩi CTS), nút sẽ đi vào backoff với một hàm mũ nhị phân gia tăng cửa sổ backoff. Tương tự, nếu nĩ nhận được một CTS khơng đi tới nĩ, nĩ cũng sẽ đi vào backoff. Nếu khơng cĩ gĩi CTS nào vừa nhận được sau 5 lần thử lại, quá trình truyền sẽ bị huỷ bỏ. Hơn nữa, nếu một nút nghe thấy một CTS trước bất kỳ quá trình truyền của nĩ, nĩ sẽ trì hỗn truyền với thời gian một gĩi tin để tránh làm hỏng lưu lượng. 2.2.3.4. Cơ chế điều khiển tốc độ Sự căng thẳng giữa lưu lượng dữ liệu gốc và lưu lượng dữ liệu định tuyến cĩ một tác động trực tiếp trong việc đạt được mục tiêu cơng bằng. Kiểm sốt truy cập mơi trường phải hỗ trợ trong việc làm cân bằng sự căng thẳng đối với kênh. Cụ thể, MAC sẽ kiểm sốt tốc độ dữ liệu gốc của một nút để cho phép lưu lượng dữ liệu định tuyến truy cập kênh và tìm kiếm trạm cơ sở. Tương tự, một vài dạng của cơ chế phát tín hiệu tăng dần lên sẽ tồn tại trong lưu lượng dữ liệu định tuyến, như vậy áp lực trở lại cĩ thể lan truyền sâu vào trong mạng đối với các nút đĩ tiến tới tốc độ của chúng thấp hơn của dữ liệu gốc. Điều này sẽ giảm tồn bộ lưu lượng dữ liệu định tuyến và mở ra kênh cho các nút gần hơn đến trạm cơ sở khởi nguồn từ dữ liệu. Như vậy cơ chế kiểm sốt tốc độ sẽ chỉ dùng thuật tốn phân phối cục bộ. Một cơ chế ẩn được đưa ra thụ động làm thích nghi tốc độ truyền thơng của cả hai lưu lượng dữ 53 liệu gốc và định tuyến, mà khơng sử dụng bất kỳ gĩi tin điều khiển MAC nào. Ý tưởng sửa lại kiểm sốt tốc độ rất đơn giản và cĩ thể được giải thích với tương tự độ đo lưu lượng dữ liệu lên trên một đường trục nơi mà lưu lượng dữ liệu định tuyến giống như lưu lượng dữ liệu trên đường trục và mỗi node bắt nguồn dữ liệu giống như các ơ tơ đang cố gắng đi vào. Theo định kỳ, một nút cố gắng đưa vào một gĩi tin. Nếu gĩi tin đĩ được đưa vào thành cơng, nĩ sẽ trở thành một phần của lưu lượng dữ liệu định tuyến. Khi nĩ được định tuyến bởi nút cha của nĩ, nĩ báo hiệu rằng đường vẫn cịn dung lượng cho nhiều lưu lượng khác và từ đĩ, một nút cĩ thể tăng tốc độ truyền của nĩ. Tuy nhiên, nếu việc đưa vào gĩi tin đĩ khơng thành cơng, nĩ báo hiệu rằng đường đang tắc và nút sẽ giảm tốc độ bắt đầu dữ liệu của nĩ và backoff để đạt được một giai đoạn thay đổi hiệu quả. Sự giải thích ở trên về tốc độ bắt đầu dữ liệu thích nghi với lưu lượng dữ liệu định tuyến như thế nào. Lưu lượng dữ liệu đinh tuyến sẽ thích nghi với lưu lượng bắt đầu dữ liệu sử dụng một cơ chế tương tự. Nếu một nút đưa vào lạc mất lưu lượng gốc trong đường trục, lưu lượng định tuyến sẽ bị cản trở và từ đĩ, tốc độ truyền lưu lượng định tuyến sẽ giảm (Các ơ tơ ở phía sau phải chậm lại so với các ơ tơ ở phía trước khi chúng trên cầu). Nĩ cĩ một domino hiệu quả trong việc lan truyền trở lại với áp lực đẩy sâu vào trong mạng điều này cuối cùng làm giảm khối lượng tồn bộ lưu lượng dữ liệu định tuyến. Độ đo hiệu quả tương tự ở trên cĩ thể thiết lập bằng một lịch trình chung. Cho rằng mỗi nút cĩ một hiểu biết hồn chỉnh về tồn bộ số lượng N nút trong tồn mạng, mỗi nút cĩ thể đo tốc độ của nĩ bằng Dung lượng kênh /N để đạt được mục tiêu cơng bằng của chúng. Tuy nhiên, bản chất Ad Hoc tự phát trong các mạng cảm biến làm cho kiến thức chung khơng thực tế như vậy. Từ đĩ, một cơ chế thích nghi cố gắng xấp xỉ nĩ được đưa ra. Cơ chế kiểm sốt tốc độ sử dụng tăng tuyến tính và giảm theo cấp số nhân gần như để kiểm sốt tốc độ truyền của ứng dụng. Cho tốc độ truyền ứng dụng là S, tốc độ thực tế bắt đầu dữ liệu là S*p ở đĩ p[0, 1]. Sự kiểm sốt tốc độ này là cĩ khả năng xảy ra, ở đĩ p là khả năng xảy ra truyền dữ liệu. Để tăng tốc độ tuyến tính, đơn giản là tăng p bởi một hằng số α . Để giảm theo cấp số nhân, nhân p bởi một trọng số β với 0 < β < 1. Nĩi tĩm lại, một α lớn thường 54 hướng đến sự linh hoạt để cạnh tranh trong kênh. β kiểm sốt hình phạt cho một lỗi truyền. Sự sụt giảm lưu lượng định tuyến được xem xét như sự lãng phí tài nguyên mạng, và sự ưu tiên cho lưu lượng định tuyến bằng cách hình phạt của nĩ ít hơn 50% (ví dụ: β định tuyến = 1.5 * β bắt đầu). Hơn nữa, một nút sẽ cho một tỷ lệ cơng bằng về băng thơng của nĩ cho mỗi nút định tuyến thơng qua nĩ. Nếu một nút cĩ một lưu lượng định tuyến từ n nút con, băng thơng bắt đầu dữ liệu của nĩ sẽ là 1/(n+1) để đạt được mục đích cơng bằng. Khi một nút cĩ thể ước lượng n bằng cách quan sát lưu lượng định tuyến, α bắt đầu cĩ thể đặt bằng α định tuyến /(n + 1). Với sự lựa chọn này, cơ chế thích nghi chỉ cĩ hai tham biến α và β. Số lượng tính tốn của cơ chế cĩ khả năng thích nghi này là nhỏ và trong khả năng tính tốn của mạng cảm biến. Nĩ yêu cầu một bộ sinh số ngẫu nhiên giả đơn giản và một vài phép tốn nhân và chia. Hơn nữa, cơ chế được tính tốn hồn tồn, điều này làm chi phí năng lượng rẻ hơn các phép tốn trên sĩng vơ tuyến. 2.2.3.5. Vấn đề nút ẩn đa chặng Cơ chế kiểm sốt đường truyền cĩ khả năng thích nghi cố gắng để tránh vấn đề nút ẩn dứt khốt khơng kiểm sốt các gĩi tin bằng cách điều chỉnh khơng đổi tốc độ truyền và thực hiện giai đoạn thay đổi, do đĩ tồn bộ luồng cĩ chu kỳ của lưu lượng dữ liệu sẽ khơng lặp lại xung đột lẫn nhau. Cơ chế RTS/CTS điều khiển tranh chấp cĩ thể giải quyết vấn đề ẩn với một vài mức độ. Tuy nhiên, MACAW cĩ đề nghị một kịch bản ở đĩ vấn đề node ẩn đa chặng khơng thể giải quyết do thiếu thơng tin đồng bộ đã biết khi mà chu kỳ xung đột giữa một nút con và nút ơng của nĩ. Nếu chúng ta giả sử rằng các gĩi tin sẽ được định tuyến sau một thời gian xử lý x, một nút con là cĩ khả năng tránh vấn đề nút ẩn với nút ơng của nĩ. Ý tưởng là nếu một nút con nghe thấy kết thúc truyền tại thời điểm t của nút cha, nĩ sẽ chờ đợi ơng của nĩ sẽ định tuyến gĩi tin của cha nĩ được bắt đầu tại thời điểm t + x. Vì vậy, nếu nút con cĩ thể hạn chế từ quá trình truyền bằng thời gian t tới t + x + thời gian gĩi tin, vấn đề nút ẩn cĩ thể được giảm. Trong thực tế, nếu nút con phát hiện tình huống như vậy nĩ sẽ thực hiện backoff để làm 55 thay đổi giai đoạn của nĩ như vậy sẽ khơng bắt gặp tình huống tương tự trong quá trình nĩ truyền kế tiếp. 2.2.4. Cơ chế MACAW( Media Access Protocol for Wireless LAN’s) MACAW [10] tập trung vào vấn đề cơng bằng cho mỗi luồng gây ra theo các cách khác nhau trong việc tranh chấp cửa sổ ở mỗi nút và đề xuất một cơ chế ở đĩ số lần backoff đã được thay đổi và sao chép giữa các nút để tạo ra những cơ hội cân bằng truy nhập kênh. Cơ chế này cĩ hiệu quả với những vấn đề cơng bằng nút trong giới hạn ngắn và dài nhưng khơng đúng khi khơng cơng bằng cho mỗi luồng. Để giải quyết vấn đề cơng bằng cho mỗi luồng, MACAW cũng đề xuất một cơ chế trong đĩ mỗi nút tuân theo một cách đếm backoff cho mỗi luồng. 2.2.4.1. Các quy tắc điều khiển và trao đổi thơng báo Mục đích của MACAW là để tính tốn lại một vài sự lựa chọn thiết kế cơ bản trong MAC và sau đĩ đưa ra một phiên bản được sửa lại phù hợp với mạng LAN khơng dây. Thuật tốn MACAW là một thiết kế sơ bộ và đưa ra nhiều dữ liệu khơng xác định. MACAW cũng cĩ thể được mơ tả trong các điều kiện về các quy tắc điều khiển, quy tắc trì hỗn và các quy tắc chờ đợi. Một bộ đệm đang chạy MACAW cĩ thể là một trong tám trạng thái sau: rỗi (IDLE), tranh chấp (CONTEND), chờ đợi CTS (WFCTS - Wait For CTS), chờ đợi tranh chấp (WFCntend - Wait for Contend), chờ đợi gửi dữ liệu (WFDS - Wait For DataSend), chờ đợi dữ liệu (WFData - Wait For Data), chờ đợi ACK (WFACK - Wait For ACK) và yên lặng (QUIET). Các quy tắc điều khiển như sau: 1. Khi A trong trạng thái IDLE và muốn truyền một gĩi tin dữ liệu đến B, nĩ thiết lập một bộ đếm thời gian ngẫu nhiên và đi đến trạng thái CONTEND. 2. Khi trạm B trong trạng thái IDLE và nhận một gĩi tin RTS từ A, nĩ truyền một gĩi tin CTS. B thì thiết lập bộ đếm thời gian và đi đến trạng thái WFDS. 3. Khi A trong trạng thái WFCTS và nhận một gĩi tin CTS từ B, nĩ xĩa bộ đếm thời gian, truyền quay trở lại gửi dữ liệu (DS-Data Send) 56 theo sau bằng các gĩi tin dữ liệu đến B. A sau đĩ vào trạng thái WFACK và thiết lập bộ đếm thời gian. 4. Khi B trong trạng thái WFDS và nhận một gĩi tin DS từ A, nĩ đi đến trạng thái WFData và thiết lập bộ đếm thời gian. 5. Khi B trong trạng thái WFData và nhận một gĩi tin từ A, nĩ xĩa bộ đếm thời gian, truyền lại một gĩi tin ACK và đi đến trạng thái IDLE 6. Khi A trong trạng thái WFACK và nhận một gĩi tin ACK từ B, nĩ khởi động lại trạng thái IDLE và xĩa bộ đếm thời gian. 7. Khi B trong trạng thái IDLE và nhận một RTS với một gĩi tin dữ liệu nĩ báo nhận lần cuối, nĩ gửi lại một ACK thay thế CTS. 8. Nếu A nhận một RTS khi nĩ trong trạng thái CONTEND, nĩ truyền gĩi tin CTS tới bên gửi và đi đến trạng thái WFDS và thiết lập bộ đếm thời gian, 9. Nếu C trong trạng thái QUIET và nhận một RTS nĩ đi đến trạng thái WFContend. 10. Nếu một trạm trong trạng thái IDLE và nhận một gĩi tin yêu cầu tới RTS, nĩ truyền một gĩi tin RTS đến bên gửi, đi đến trạng thái WFCTS và thiết lập một giá trị bộ đếm thời gian. Các quy tắc trì hỗn cho như sau: 1. Khi C nghe thấy một gĩi tin RTS từ A đến B, nĩ đi từ trạng thái hiện tại của nĩ đến trạng thái QUIET và thiết lập một giá trị bộ đếm thời gian đủ cho A nghe thấy CTS của B. 2. Khi C nghe thấy một gĩi tin DS từ A đến B, nĩ đi từ trạng thái hiện tại của nĩ đến trạng thái QUIET và thiết lập một bộ đếm thời gian đủ cho A để truyền gĩi tin dữ liệu và sau đĩ nghe ACK của B. 3. Khi D nghe thấy một gĩi tin CTS từ B đến A, nĩ đi từ trạng thái hiện taị của nĩ đến trạng thái QUIET và thiết lập một giá trị bộ đếm thời gian đủ cho B để nghe thấy dữ liệu của A. 4. Khi B nghe thấy một gĩi tin yêu cầu RTS từ D, nĩ đi từ trạng thái 57 hiện tại của nĩ đến trạng thái QUIET và thiết lập một giá trị bộ đếm thời gian đủ để trao đổi RTS - CTS. Các quy tắc chờ đợi cho như sau: 1. Khi một trạm trong trạng thái WFContend và bộ đếm thời gian hết hạn, nĩ thiết lập một bộ đếm thời gian ngẫu nhiên và đi đến trạng thái CONTEND. 2. Khi một trạm trong trạng thái CONTEND và bộ đếm thời gian hết hạn, nĩ cĩ thể hoặc truyền một gĩi tin CTS để thực hiện truyền dữ liệu bắt đầu - gửi (A) hoặc một gĩi tin yêu cầu RTS để thực hiện truyền dữ liệu bắt đầu - nhận (D), phụ thuộc vào hoặc nĩ vào trạng thái CONTEND từ trạng thái IDLE, hoặc từ trạng thái WFContend. Với truyền dữ liệu bắt đầu - gửi, A truyền một gĩi tin RTS, bao gồm ID trạm của A và B, và một số lượng yêu cầu các byte để gửi. A đi đến trạng thái WFCTS và thiết lập giá trị bộ đếm thời gian. Với truyền dữ liệu bắt đầu - nhận, D truyền một gĩi tin yêu cầu RTS và sau đĩ đi đến trạng thái IDLE. 3. Từ bất kỳ trạng thái khác nào, khi bộ đếm thời gian hết hạn, một trạm đi đến trạng thái IDLE và khởi động lại giá trị bộ đếm thời gian. 2.2.4.2. Các quy tắc Backoff và sao chép Mỗi trạm giữ một trong các biến sau: 1. my_backoff : giá trị backoff tại trạm này. 2. Với mỗi bộ đệm ở xa :  local_backoff: giá trị backoff tại trạm này được đánh giá bởi trạm ở xa  remote_backoff: đánh giá giá trị backoff cho một trạm ở xa.  exchange_seq_number (ESN) : Một chuỗi số được sử dụng trong việc trao đổi gĩi tin với trạm ở xa.  retry _count: số lượng truyền lại. 58 Khi một bộ đệm P nghe thấy một gĩi tin, khác hơn một RTS, từ Q đến R, P cập nhật đánh giá của nĩ về các mức tranh chấp của Q và R bởi sự sao chép các giá trị local_backoff và remote_backoff được mang trong gĩi tin, tương ứng. Thêm vào đĩ, P cũng sao chép giá trị backoff của Q và của chính nĩ, giả sử rằng Q là trạm xung quanh mà tại đĩ backoff của Q được cho là phản chiếu lại mức độ tắc nghẽn xung quanh láng giềng. Các gĩi tin RTS bị lờ đi bởi vì chúng cĩ thể khơng mang các giá trị backoff chính xác. Chính xác hơn: packet (local_backoff, remote_backoff, ESN) if packet = = RTS, ignore else backoff (của Q) = local_backoff; if (remote_backoff ! = I_DONT_KNOW) backoff (của P)= remote_backoff; my_backoff = local_backoff; Khi một bộ đệm P nhận được một gĩi tin từ bộ đệm Q đến P, nếu exchange_seq_number cĩ giảm, hoặc gĩi tin được khởi tạo một sự truyền mới hoặc một thủ tục bắt tay thành cơng. Trong trường hợp này, các giá trị backoff được mang trong gĩi tin sẽ là các giá trị chính xác. Do P cập nhật các giá trị backoff nĩ sở hữu và của Q, giảm ESN và khởi động lại retry_count. Ở đây local_backoff của P là một biến được dùng tạm thời khi cố gắng thay đổi với Q; giá trị của nĩ đồng bộ với my_backoff của P khi một thủ tục bắt tay thành cơng. Trái lại, nếu một gĩi tin là một sự truyền lại của một gĩi tin cũ, P giả sử xung đột xuất hiện tại điểm kết thúc của Q, và tăng giá trị backoff của Q tương ứng. Vì tổng các giá trị backoff của hai điểm kết thúc sẽ độc lập như nhau tại mỗi điểm kết mà xung đột xuất hiện, P cập nhật giá trị backoff của nĩ như sự khác biệt giữa tổng số và giá trị backoff của Q (khi P đánh giá) packet (local_backoff, remote_backoff, ESN) If (ESN > ESN (đối với Q)) 59 backoff (của Q) = local_backoff; if (remote_backoff ! = I_DONT_KNOW) local_backoff (của P) = remote_backoff; my_backoff = remote_backoff; else local_backoff (của P) = my_backoff; ESN (của P đối với Q) = ESN+ 1; retry_count (của P với Q) = 1; else /* một gĩi tin được truyền lại*/ backoff (của Q)= local_backoff + retry_count * ALPHA; if (remote_backoff != I_DONT_KNOW) local_backoff (của P) = (local_backoff + remote_backoff) – backoff (của Q); else local_backoff (của P) = my_backoff; retry_count + +; Khi bộ đệm P gửi một gĩi tin tới bộ đệm Q, nĩ gán các giá trị tham số trong gĩi tin, local_backoff, remote_backoff, và ESN theo cách sau đây: If (packet = RTS) /* hoặc nĩ cần phải bắt đầu một gĩi mới*/ local_backoff (được sử dụng trong giao tiếp với Q) = my_backoff; remote_backoff = backoff (của Q); local_backoff = local_backoff (được sử dụng với Q); Gửi gĩi tin với local_backoff, remote_backoff, ESN; Khi một bộ đệm P hết thời gian trong một gĩi tin tới bộ đệm Q: Backoff (của Q) + = retry_count * ALPHA; If trong phạm vi max_retry_count, local_backoff (của P được sử dụng với Q) = MAX_BACKOFF; 60 backoff (của Q) = I_DONT_KNOW; 2.2.5. Chuẩn IEEE 802.11e MAC IEEE 802.11e MAC [12] là một bổ sung xuất hiện trong tiêu chuẩn IEEE 802.11 của mạng cục bộ khơng dây (WLAN) để hỗ trợ chất lượng dịch vụ (QoS). Nĩ dựa trên hai cơ chế là điều khiển trung tâm và truy cập kênh dựa trên tranh chấp. Trong đĩ cơ chế truy cập kênh dựa trên tranh chấp kế thừa DCF được gọi là tăng cường chức năng phối hợp phân tán (EDCF – Enhanced DCF). EDCF cung cấp sự truy cập kênh phân biệt tới các khung với các quyền ưu tiên khác nhau. Với EDCF, một MAC cĩ thể cĩ nhiều hàng đợi làm việc độc lập, song song, với các mức độ ưu tiên khác nhau. Các khung với mức độ ưu tiên khác nhau được truyền sử dụng các tham số tranh chấp CSMA/CA khác nhau. Với EDCF, một trạm khơng thể truyền một khung mà khuếch tín hiệu một khoảng thời gian được gọi là giới hạn cơ hội truyền (TXOP – transmission opportunity). Nếu một khung quá dài được truyền trong một TXOP, nĩ sẽ được phân đoạn thành nhiều các khung. Ngồi ra một tính năng tuỳ chọn của EDCF được gọi là nhĩm khơng tranh chấp (CFB - contention- free burst), tính năng này giúp tăng cường hiệu suất EDCF bằng việc gia tăng lưu lượng của tồn bộ hệ thống và bảo đảm nhiều luồng cĩ chất lượng chấp nhận được trong các điều kiện về khung bị mất và độ trễ. Như vậy, IEEE 802.11e MAC cũng đã đề xuất một kế hoạch tương tự với MACAW để ưu tiên những luồng tại một nút. Mặc dù điều này hiệu quả khi mạng khơng xảy ra tắc nghẽn đối với các luồng, hạn chế chính của cơ chế này là nếu số luồng tăng lên, sự tranh chấp giữa những luồng truy cập kênh cũng tăng cao lên, và như vậy nĩ làm giảm giá trị nhiễu sĩng vơ tuyến và mơi trường tiện ích. 61 CHƯƠNG III GIẢI PHÁP CẢI THIỆN SỰ CƠNG BẰNG TRONG CÁC MẠNG AD HOC KHƠNG DÂY 3.1. Giải pháp cải thiện sự cơng bằng cho mỗi luồng trong tầng liên kết Khi phân tích về sự đảm bảo cơng bằng trong các mạng khơng dây, tầng liên kết cĩ một tác động quan trọng trong các vấn đề cơng bằng cho mỗi luồng. Để giải quyết vấn đề khơng cơng bằng cho mỗi luồng xảy ra tại tầng liên kết, một giải pháp là sử dụng bộ lập lịch RR (Round Robin) để thay thế cho bộ lập lịch FIFO truyền thống. So sánh với bộ lập lịch FIFO truyền thống, bộ lập lịch RR cung cấp sự cơng bằng cho mỗi luồng tốt hơn. Trong bộ lập lịch FIFO, tất cả các gĩi tin được lưu trữ trong một bộ đệm riêng và truyền ra ngồi theo trình tự mà chúng được lưu trữ. Bởi vậy, nếu các gĩi tin khơng được lưu giữ cơng bằng, chúng sẽ khơng truyền tới tầng MAC theo một cách cơng bằng. Trái với điều này, trong bộ lập lịch RR, nĩ duy trì bộ đệm riêng biệt đối với mỗi luồng và gửi một gĩi tin từ mỗi bộ đệm một cách lần lượt. Điều này cho phép bộ lập lịch RR gửi nhiều gĩi tin tới tầng MAC một cách cơng bằng cho mỗi luồng. Như vậy, khi một gĩi tin mới đến tại tầng liên kết, gĩi tin được chèn vào một vùng đệm thích hợp bằng cách kiểm tra thơng tin về socket của nĩ trong phần đầu của gĩi tin (với địa chỉ IP và số cổng của máy chủ đầu cuối). Sau đĩ những gĩi tin tại đầu của mỗi vùng đệm được truyền lần lượt tới tầng MAC. Tầng MAC sẽ cung cấp một cơ chế cho phép một nút gửi vài gĩi tin thuộc về các luồng khác nhau trong một truy nhập kênh đơn khi nĩ giành được kênh. Số lượng gĩi tin gửi trong một truy nhập kênh đơn là khơng thay đổi tại tầng liên kết. Quá trình này cĩ thể được mơ tả thơng qua một giải thuật để xác định số lượng những luồng như sau: Đầu tiên, một yêu cầu được gửi đi để xác nhận số lượng các luồng dữ liệu đang tới vùng đệm. Bằng sự kiểm tra từng bộ đệm xem cĩ gĩi tin nào đã được lưu giữ trong đĩ, mục đích để xác định số vùng đệm khơng trống. Sau 62 đĩ, số lượng gĩi tin gửi trong một truy cập kênh đơn là khơng thay đổi với giá trị nhỏ nhất giữa số lượng vùng đệm khơng trống và số gĩi tin cực đại được gửi đi trong một truy nhập kênh đơn. Hình 3.1. Giải thuật xác định số lượng những luồng Đặt Max_flow làm đại diện cho số gĩi tin cực đại được gửi đi trong một truy nhập kênh đơn. Max_flow được gửi đi trong một truy cập kênh đơn phụ thuộc vào điều kiện của vùng mạng thuộc về cùng một nút. Max_flow cần phải đặt đủ thấp trong điều kiện vùng mạng đang tập trung nhiều nút. Mặt khác, Max_flow cần phải được đặt đủ cao trong điều kiện ngược lại. Việc thiết lập này cần phải được xác định chính xác bởi vì nếu Max_flow tại một nút được đặt quá cao khi mạng đang tập trung đơng, nĩ cĩ thể cản trở các nút khác 63 thu nhận kênh với những chu kỳ thời gian dài hơn, dần dần làm giảm sút hiệu suất mạng. Bởi vậy, nếu số luồng cực đại tại một nút lớn hơn Max_flow, nút đĩ gửi Max_flow gĩi tin trong một truy nhập kênh đơn. Trong trường hợp này, mặc dù cơng bằng cho mỗi luồng cĩ thể đã suy giảm, nhưng bằng việc sử dụng bộ lập lịch RR cĩ thể vẫn cải thiện cơng bằng cho mỗi luồng. Max_flow phụ thuộc nhiều nhân tố như độ rộng dải thơng truyền, điều kiện kết nối khơng dây, hình trạng mạng và số lượng luồng chia sẻ băng thơng. Cho rằng sự ảnh hưởng của những nhân tố là như nhau với tất cả các nút nằm trong các dải truyền dẫn khác nhau, và sau đĩ giả thiết rằng mỗi nút giữ Max_flow như nhau. 3.2. Giải pháp cải thiện sự cơng bằng cho mỗi luồng trong tầng MAC Một nút được cho phép để gửi một vài gĩi tin của các luồng khác nhau bất cứ khi nào mà nĩ thu nhận kênh. Trong cơ chế DCF gốc, khi một nút gửi thành cơng một gĩi tin, nĩ thực hiện một giải thuật backoff (khi truyền thành cơng, một nút backoff trong một khoảng thời gian nhất định, khơng chú ý đến nĩ cịn cĩ các gĩi tin khác cần gửi đi). Tuy nhiên cơ chế này cung cấp việc truy nhập kênh khơng cơng bằng giữa các luồng nhất là tại nơi cĩ sự khác nhau về số lượng các luồng tại các nút di động mà nằm trong cùng phạm vi truyền. Để giải quyết vấn đề này một giải pháp được sử dụng cho phép một nút cĩ nhiều luồng, được gửi một vài gĩi tin mà khơng cần thực hiện giải thuật backoff nhưng chỉ chờ đợi DIFS giữa mỗi phiên truyền. Quá trình này cĩ thể được mơ tả thơng qua giải thuật truyền gĩi tin tại tầng MAC như sau: Theo như giải thuật truyền gĩi tin tại tầng MAC cho thấy nếu như một gĩi tin được truyền thành cơng và một gĩi tin khác thuộc về một luồng khác đã tồn tại, một nút khơng thể thực hiện giải thuật backoff nhưng sẽ gửi nĩ sau khi chờ đợi DIFS. Bằng việc lặp lại giải thuật này, một nút cĩ thể gửi vài gĩi tin của các luồng khác nhau trong một truy nhập kênh đơn. 64 Hình 3.2. Giải thuật truyền gĩi tin Một thao tác truy nhập kênh khi cơ chế DCF gốc được thay đổi để phù hợp với mơ hình mạng đã trình bày trong hình 2.2. Hình 3.3. Một thao tác truy nhập kênh đợi DIFS Theo mơ hình trình bày trong hình 2.2, S2 là nguồn gửi của hai luồng cho nên, nĩ gửi một gĩi tin từ mỗi luồng trong một truy nhập kênh đơn. Như vậy, giải pháp tại tầng MAC sẽ cung cấp cách truy nhập kênh như nhau đối với mỗi luồng và do đĩ đạt được sự cơng bằng cho mỗi luồng. Trì hỗn truy cập Trì hỗn truy cập Trì hỗn truy cập Flow0 Flow0 S0 S2 Flow1 Flow1 Flow2 Flow2 Trì hỗn truy cập DIFS DIFS Thời gian Thời gian 65 3.3. Phân tích những đặc trưng của giải pháp cải thiện sự cơng bằng Những giải pháp đưa ra nhằm mục đích đảm bảo sự cơng bằng cho mỗi luồng trong mạng Ad Hoc khơng dây. Bởi vậy, chúng được đánh giá dựa trên hai tiêu chí đĩ là phân tích sự cơng bằng và những đặc trưng mơi trường tiện ích. 3.3.1. Đánh giá phân tích sự cơng bằng cho mỗi luồng Để đo sự cơng bằng trong một hệ thống với nhiều luồng, một độ đo được sử dụng để chỉ ra chỉ số cơng bằng cho mỗi luồng [13]. Cơng thức về chỉ số cơng bằng như sau: FairnessIndex = Avgn AvgT n i i )1(2 1 1      (6) ở đây, n là số lượng các luồng, Ti là thơng lượng của luồng i, và Avg là thơng lượng trung bình đạt được của tất cả n luồng. Như định nghĩa ở trên, FairnessIndex được trình bày bởi những thuộc tính sau đây:  FairnessIndex được xác định bằng cách lấy một giá trị trong khoảng từ 0 đến 1 cho bất cứ số lượng các luồng. Khi mạng đã hồn tồn cơng bằng cho mỗi luồng (tất cả các luồng cĩ cùng thơng lượng), FairnessIndex là 1. Ngược lại, nĩ nhận giá trị 0 khi mạng hồn tồn khơng cơng bằng (một luồng chiếm tất cả dải thơng và những luồng cịn lại khơng được sử dụng).  Nĩ liên tục (mỗi thay đổi trong thơng lượng của bất cứ luồng nào ảnh hưởng tới giá trị của chỉ số).  Đơn vị của phép đo khơng ảnh hưởng tới chỉ số.  Nếu như ngồi n luồng, k là sự chia sẻ tương đương tồn bộ băng thơng và n – k cịn lại là rỗi, FairnessIndex là (k-1)/(n-1) Tử số của phân số trong cơng thức là tổng giá trị tuyệt đối khác nhau của thơng lượng mỗi luồng từ thơng lượng trung bình. Tổng này càng lớn, hệ thống càng khơng cơng bằng, khi những thơng lượng riêng biệt lệch so với giá trị trung bình. Trong trường hợp xấu nhất, một luồng là luồng duy nhất hoạt động trong khi tất cả các luồng khác đang rỗi. Trong trường hợp này, hiệu số tuyệt 66 đối với mỗi luồng rỗi sẽ là Avg (khi Ti = 0), trong khi luồng đang hoạt động, hiệu số tuyệt đối sẽ là (n-1)*Avg. Tổng của n-1 số hạng đầu tiên là (n-1)*Avg. Cộng hiệu số tuyệt đối cho luồng đang hoạt động, sẽ là 2(n-1)*Avg, đây là giá trị được phân chia phù hợp với kết quả chuẩn hố. Do đĩ, mẫu số của phân số là giá trị tuyệt đối khác nhau của thơng lượng mỗi luồng từ thơng lượng trung bình trong trường hợp này mạng ở đây là hồn tồn khơng cơng bằng. Để so sánh những đặc tính cơng bằng của cơ chế gốc và giải pháp đưa ra, mơ hình mạng trong hình 2.2 được xem xét. Tỷ lệ lưu lượng truy cập tại những nguồn gửi là bằng G, và băng thơng mơi trường trung bình cực đại là B. Giả sử rằng vùng đệm tại nút S1 được chia sẻ cơng bằng bởi Flow1 và Flow2 (điều này cĩ nghĩa là các gĩi tin được gửi đến tầng MAC theo một cách cơng bằng cho mỗi luồng ), các thơng lượng đạt được bởi Flow1 và Flow2 là xấp xỉ bằng nhau. Biểu diễn các thơng lượng của Flow1 và Flow2 là Th(Flow1) và thơng lượng của Flow0 là Th(Flow0). Trước tiên, FairnessIndex được tính tốn khi cơ chế gốc được điều chỉnh phù hợp với mơ hình mạng. Từ đĩ cơ chế gốc là cơng bằng cho mỗi nút, các thơng lượng đạt được bởi mỗi luồng là:               ) 2 B G ( 4 B= , 2 B ) 2 B <G 3 B ( 2 G-B= G, ) 3 B G ( G = nÕu nÕu nÕu Th(Flow1) = Th(Flow0) )7(Th(Flow1) = Th(Flow0) Th(Flow1) = Th(Flow0) Từ (6) và (7), FairnessIndex của mơ hình đối với cơ chế gốc là: FairnessIndex=               ) 2 B G ( , 4 3 ) 2 B <G 3 B ( , 2B G)-3(B ) 3 B G ( 1, nÕu nÕu nÕu )8( 67 Bây giờ FairnessIndex được tính tốn khi mà các giải pháp ở trên được điều chỉnh phù hợp với mơ hình mạng trong hình 2.2. Như hình 3.3 cho thấy, cơ chế đưa ra cho phép phân chia băng thơng cơng bằng tới mỗi luồng, và từ đĩ thơng lượng của mỗi luồng là bằng nhau (Th(Flow0) = Th(Flow1) = Th(Flow2)), FairnessIndex giữ lấy 1 trong tồn bộ phạm vi của G. Dựa trên những kết quả này, so sánh FairnessIndex của mỗi cơ chế được minh hoạ với hai mơ hình mạng. Rõ ràng, các giải pháp đưa ra cải thiện đáng kể cơng bằng cho mỗi luồng. Hình 3.4. FairnessIndex của mỗi cơ chế với mơ hình mạng trong hình 2.1 Hình 3.5. FairnessIndex của mỗi cơ chế với mơ hình mạng trong hình 2.2 3.3.2. Đánh giá phân tích đối với mơi trường tiện ích Mơi trường tiện ích là một đặc trưng quan trọng đối với một mạng ở đĩ các nút chia sẻ mơi trường khơng dây. Để đo mơi trường tiện ích, cơng thức tính tốn thời gian trung bình được sử dụng để truyền một gĩi tin như sau: Mơi trường tiện ích =  %100 gian thêi sè Tỉng dơng sư gian Thêi (9) FairnessIndex Cơ chế đưa ra B/3 G Cơ chế gốc 1 B/2 3/4 FairnessIndex Cơ chế đưa ra B/2 G Cơ chế gốc 1 68 ở đĩ Thời gian sử dụng khơng bao gồm thời gian dùng cho những lần truyền thất bại bởi xung đột. Cơ chế gốc yêu cầu các nút thực hiện một giải thuật backoff mỗi khi kết thúc truyền. Mặt khác, các giải pháp đưa ra cho phép các nút truyền vài gĩi tin mà khơng cần thực hiện giải thuật backoff giữa mỗi phiên truyền. Như vậy, nĩ đã làm sáng tỏ rằng, trái với cơ chế gốc, các giải pháp đưa ra làm giảm bớt chi phí thời gian tham gia thực hiện một vài cơ chế backoff. Vì thế, Thời gian sử dụng được tăng lên dẫn đến sự cải thiện về mơi trường tiện ích. Do đĩ, nĩ dẫn đến cải thiện tồn bộ sự thực thi của mạng. 3.4. Đánh giá các giải pháp thơng qua mơ phỏng Các giải pháp đưa ra sẽ được dựa trên đánh giá bằng những mơ phỏng sử dụng bộ mơ phỏng mạng ns-2. Bảng dưới đây cho thấy những tham số được sử dụng cho bộ mơ phỏng như sau: Bảng 3.1. Các tham số mơ phỏng Thời gian mơ phỏng 50 s Kiểu Antenna Ommi directional Mơ hình lan truyền Free space & Two-ray Dải truyền 250 m Giao thức MAC IEEE 802.11b (RTS/CTS) Băng thơng mơi trường cực đại 2 MBit/s Kiểu vùng đệm FIFO, RR Kích thước vùng đệm 50 pkts Giao thức định tuyến DSDV Kiểu lưu lượng UDP/CBR, TCP/FTP Khoảng cách gĩi tin CBR 1-20 ms Kích thước cửa sổ cực đại TCP 20 pkts Kích thước gĩi tin 512 byte, 1Kbyte 69 Các đặc trưng được đánh giá với cả hai lưu lượng UDP/CBR và TCP/IP bao gồm thơng lượng của những luồng riêng biệt, tổng thơng lượng của mạng, cơng bằng cho mỗi luồng, và mơi trường tiện ích. Để đo được cơng bằng cho mỗi luồng và mơi trường tiện ích, độ đo được trình bày bởi (6) và (9) được sử dụng. Giả thiết rằng trong vấn đề cơng bằng, những mơ hình mạng chỉ xem xét khi ở đĩ tất cả lưu lượng cĩ tỷ lệ truyền tin giống nhau. Bằng mơ phỏng, những đặc trưng của giải pháp đưa ra được so sánh với hai cơ chế gốc là cơ chế FIFO và cơ chế RR. Bảng 3.2. Các đặc trưng riêng biệt của mỗi giải pháp Các giải pháp Tầng liên kết Tầng MAC Cơ chế FIFO Bộ lập lịch FIFO IEEE 802.11 b Cơ chế RR Bộ lập lịch RR IEEE 802.11 b Cơ chế đưa ra Bộ lập lịch RR Sự phối hợp Như bảng 2 cho thấy, cả hai cơ chế gốc sử dụng IEEE 802.11 b tại tầng MAC. Tuy nhiên, trong tầng liên kết, cơ chế FIFO sử dụng FIFO làm cơ chế lập lịch, trong khi cơ chế RR sử dụng RR làm cơ chế lập lịch. Trong cơ chế đưa ra, số lượng gĩi tin tối đa được gửi trong một truy cập kênh đơn (Max_flow) được cố định là 4. Hai kiểu mơ hình mạng được sử dụng để đánh giá khả năng thực thi đĩ là mơ hình đơn chặng (được đánh giá ở nơi mà sự khơng cơng bằng cho mỗi luồng chủ yếu gây ra bởi tầng MAC) và mơ hình đa chặng (được đánh giá tại nơi mà sự khơng cơng bằng cho mỗi luồng chủ yếu gây ra bởi tầng liên kết). 3.4.1. Mơ hình đơn chặng Cho mơ hình mạng dưới đây, trong đĩ S0 và S2 là nút gửi trong phạm vi mỗi dải truyền khác nhau, ở đĩ S0 cĩ một luồng (Flow0) và S2 cĩ n luồng (Flow1- Flow n). 70 Hình 3.6. Mơ hình đơn chặng Đầu tiên, những đặc trưng cơng bằng được đánh giá với số luồng tại nút S2 với n bằng 2. 0 50 100 150 200 250 300 350 400 FIFO RR Đưa ra T hr ou gh pu t(k bp s) Flow0 Flow1 Flow2 Hình 3.7. Thơng lượng đạt được bởi mỗi luồng trong mơ hình đơn chặng Như kết quả tại hình 3.7 cho thấy thơng lượng riêng biệt của mỗi luồng ứng với mỗi cơ chế, khi gĩi CBR (Constant Bít Rate) trong khoảng thời gian 0.01s. Sự khác nhau về thơng lượng của mỗi luồng rõ ràng nhất khi cơ chế FIFO được ứng dụng vào mơ hình mạng. Để so sánh với cơ chế FIFO, trong cơ chế RR, thơng lượng thu được bởi Flow1 và Flow2 là gần bằng nhau. Tuy 71 nhiên, thơng lượng thu được bởi Flow0 là cao hơn nhiều so với Flow1 và Flow2. Trong những cơ chế gốc, thơng lượng của Flow0 là xấp xỉ bằng với tổng các thơng lượng của Flow1 và Flow2. Trái ngược với những cơ chế gốc, cơ chế đưa ra đạt được thơng lượng bằng nhau cho mỗi luồng. Tồn bộ thơng lượng của mạng với cơ chế FIFO, cơ chế RR và cơ chế đưa ra tương ứng là 692.38 [kpbs], 692.46 [kbps], và 700.10 [kbps]. Rõ ràng, tồn bộ thơng lượng của cơ chế đưa ra cao hơn rất nhiều so các cơ chế gốc xấp xỉ khoảng 8 [kpbs]. Việc gia tăng tồn bộ thơng lượng thể hiện sự cải thiện về mơi trường tiện ích. Qua những kết quả cho thấy, cơ chế đưa ra cĩ hiệu quả trong khơng những cơng bằng cho mỗi luồng mà cịn trong tồn bộ sự thực thi của mạng. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.02 0.015 0.01 0.005 0.001 TCP CBR (sec) Fa ir ne ss In de x FIFO RR Đưa ra Hình 3.8. So sánh FairnessIndex của mỗi cơ chế trong mơ hình đơn chặng Hình 3.8 cho thấy so sánh FairnessIndex của ba cơ chế với những khoảng thời gian truyền gĩi tin CBR khác nhau từ [0.001s đến 0.02s]. Ngồi ra, kết quả về các kết nối TCP cũng cho thấy đúng như vậy. Từ kết quả trong hình cho thấy sự cơng bằng cho mỗi luồng trong cơ chế FIFO phụ thuộc vào việc gia tăng tốc độ truyền CBR. Điều này giải thích tại sao sự cơng bằng của những cơ chế chuẩn giảm sút cùng với sự gia tăng tốc độ truyền CBR tại phương trình (5). Ngược lại trong cơ chế RR, khi nĩ cung cấp dịch vụ cơng bằng cho mỗi luồng trong tầng liên kết, nĩ cĩ thể cải thiện được những đặc trưng cơng bằng tốt hơn so với cơ chế FIFO. Tuy nhiên, cơ chế RR cĩ những 72 đặc trưng cơng bằng thấp hơn so với cơ chế đưa ra bởi vì nĩ cho phép Flow0 giữ thơng lượng cao hơn nhiều so với những luồng cịn lại. Như vậy rõ ràng rằng cơ chế đưa ra cải thiện đáng kể sự cơng bằng, FairnessIndex là xấp xỉ bằng 1 trong tồn bộ phạm vi của khoảng cách đối với cả hai loại lưu lượng UDP và TCP So sánh những đặc trưng cơng bằng trong hình 3.8 và hình 3.5 với những kết quả đã thu được bằng thí nghiệp mơ phỏng và phân tích lý thuyết, lần lượt, đối với cơ chế đưa ra và cơ chế RR. Trục nằm ngang trong hình 3.5 và hình 3.8 cho thấy tốc độ truyền CBR (G) và khoảng thời gian truyền gĩi tin CBR, tương ứng. G được biểu diễn bởi t như G = t PacketSize . Khi PacketSize là một giá trị hằng số, nĩ chỉ rõ rằng sự giảm sút của t ( trục nằm ngang của hình 3.8) là tương đương với sự gia tăng của G (trục nằm ngang của hình 3.5 ). Hình 3.8 cho thấy rằng FairnessIndex của cơ chế đưa ra đạt xấp xỉ 1 trong tồn bộ dải của trục nằm ngang. Mặt khác, FairnessIndex của cơ chế RR đạt 1 về bên trái của trục nằm ngang. Sau đĩ từ từ giảm bớt xuống tới 0.75 (=3/4), và cuối cùng trở nên ổn định xung quanh 0.75. Bằng việc so sánh những đặc trưng cơng bằng đối với điều này trong hình 3.5, cho thấy rằng chúng tương tự những mẫu đặc trưng do đĩ chứng minh tính hợp lệ về sự phân tích lý thuyết. Tiếp theo, những đặc trưng cơng bằng của mỗi cơ chế đối với CBR (trong khoảng thời gian là 0.01s) được đánh giá với số luồng tại nút S2 với n bằng 4. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 CBR (sec) Fa ir ne ss In de x FIFO RR Đưa ra Hình 3.9. So sánh FairnessIndex (CBR) với số luồng tại S2 bằng 4 73 Các kết quả cho thấy rằng FairnessIndex của những cơ chế gốc đã giảm sút cùng với sự gia tăng về số lượng các luồng tại S2. Cơ chế đưa ra đã cải thiện một cách đáng kể cơng bằng cho mỗi luồng trong tồn bộ phạm vi của n. Cuối cùng, những đặc trưng mơi trường tiện ích được đánh giá khi số lượng các luồng tại S2 thay đổi từ 1 đến 4. 90 91 92 93 94 95 96 97 98 1 2 3 4 Số lượng các luồng tại S2 M ơi t rư ờ ng t iệ n íc h ( % ) FIFO RR Đưa ra Hình 3.10. So sánh mơi trường tiện ích trong mơ hình đơn chặng Như hình 3.10 cho thấy, cơ chế đưa ra đã cải thiện Mơi trường tiện ích lên tới trên 2% 3.4.2. Mơ hình đa chặng Mơ hình mạng dưới đây được đánh giá, trong đĩ S1 khởi nguồn từ Flow1 cĩ hướng tới S3, S2 khởi nguồn từ Flow2 cĩ hướng tới S3. Từ đĩ S1 và S3 khơng nằm trong cùng dải truyền với nhau, S2 được sử dụng như một nút nhảy cho Flow1. Vì vậy, vùng đệm tại S2 được chia sẻ bởi cả hai luồng. Trong mơ hình này, vấn đề chính mà sự cơng bằng cho mỗi luồng trở nên xấu đi là trên tầng liên kết. Hình 3.11. Mơ hình đa chặng 74 Khi S2 cung cấp dịch vụ chuyển tiếp tới Flow1, vùng đệm tại S2 được chia sẻ bởi cả hai luồng. Hình 3.12 mơ tả sự so sánh thơng lượng của các luồng riêng biệt khi khoảng thời gian truyền gĩi tin CBR là 0.01s. Như trong hình cho thấy, trong cơ chế FIFO cĩ thơng lượng khác nhau của mỗi luồng là rất lớn. Để so sánh với cơ chế FIFO, cơ chế đưa ra và cơ chế RR đã cĩ cải thiện cơng bằng, nhất là cơ chế RR cho thấy những đặc trưng cơng bằng tốt hơn so với cơ chế đưa ra. Điều này cĩ thể được giải thích như sau, để gửi gĩi tin theo một cách cơng bằng hồn tồn cho mỗi luồng, bộ lập lịch RR tại S2 nhận được gĩi tin gửi đi từ mỗi bộ đệm lần lượt tới Flow1 và Flow2. Nếu một trong những bộ đệm đang trống trong một khoảng thời gian, mà trong thời gian đĩ, RR chỉ gửi những gĩi tin từ vùng đệm cịn lại dẫn đến sự giảm sút về cơng bằng cho mỗi luồng. Để làm rõ hơn khi xem xét bộ đệm của Flow2 được bắt nguồn từ S2, do đĩ tốc độ được cung cấp là lớn hơn so với băng thơng trung bình. Như vậy sẽ cĩ một hoặc nhiều gĩi tin luơn tồn tại trong bộ đệm. 0 50 100 150 200 250 300 FIFO RR Đưa ra T hr ou gh pu t ( kb ps ) Flow1 Flow2 Hình 3.12. Thơng lượng đạt được bởi mỗi luồng trong mơ hình đa chặng Bây giờ, bộ đệm của Flow1 được xem xét khi cơ chế RR được ứng dụng vào mơ hình. Khi cơ chế MAC chuẩn cung cấp sự phân chia kênh cơng bằng cho mỗi luồng, S1 và S2 truyền gĩi tin theo một tốc độ xấp xỉ bằng nhau. Tuy nhiên, khi S1 cĩ một luồng Flow1 nhưng S2 cĩ hai luồng Flow1 và Flow2 để gửi đi, hiển nhiên rằng S2 nhận được Flow1 với tốc độ cao hơn so với tốc độ nĩ truyền Flow1. Do đĩ, bộ đệm cho S1 luơn cĩ gĩi tin được lưu giữ. Vì thế, 75 bộ lập lịch RR tại S2 trong cơ chế RR cĩ thể gửi các gĩi tin lần lượt từ mỗi bộ đệm, kết quả là cải thiện sự cơng bằng một cách đáng kể. Mặt khác, từ cơ chế đưa ra cung cấp sự phân chia kênh cơng bằng cho mỗi luồng, S2 nhận và gửi Flow1 với một tốc độ gần bằng nhau. Vì thế, khi S2 nhận được kênh, cĩ một khả năng rằng nĩ khơng cĩ bất kỳ gĩi tin nào của Flow1 để gửi đi. Trong trường hợp khác, S2 gửi đi chỉ những gĩi tin của Flow2. Như vậy, Flow2 đạt được một thơng lượng hơi cao hơn so với thơng lượng của Flow1. Điều này dẫn đến những đặc trưng cơng bằng cho mỗi luồng thấp hơn so với mức của cơ chế RR. Tồn bộ thơng lượng của mạng với cơ chế FIFO, cơ chế RR và cơ chế đưa ra tương ứng là 334.48 [kpbs], 334.48 [kbps], và 398.46 [kbps]. Rõ ràng, cơ chế đưa ra cải thiện tồn bộ thơng lượng với khoảng chừng 64 kBít/s. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.02 0.015 0.01 0.005 0.001 TCP CBR (sec) Fa ir ne ss In de x FIFO RR Đưa ra Hình 3.13. So sánh FairnessIndex của mỗi cơ chế trong mơ hình đa chặng Hình 3.13 cho thấy sự so sánh cơng bằng của mỗi cơ chế khi khoảng thời gian truyền gĩi tin CBR thay đổi. FairnessIndex của cơ chế FIFO giữ 0.009 và 0.005 khi khoảng thời gian truyền gĩi tin CBR là 0.005 và 0.001 giây, tương ứng. Hình 3.13 cho thấy rằng sự cơng bằng của cơ chế FIFO sụt giảm một cách đáng kể với sự gia tăng của tốc độ truyền CBR. So sánh với điều này, cơ chế RR và cơ chế đưa ra cải thiện đáng kể sự cơng bằng, FairnessIndex cao nhất đạt được là 99% đối với cơ chế RR và 92% đối với cơ chế đưa ra. Tuy nhiên, trong tất cả những cơ chế, 76 FairnessIndex với lưu lượng TCP sẽ khơng thể vượt quá 30%. Đĩ là bởi vì nguồn gửi TCP của Flow1 thường xuyên tác động trở lại với những sự mất mát ngẫu nhiên và thực thi một giải thuật điều khiển tắc nghẽn. 82 84 86 88 90 92 94 96 98 0.02 0.015 0.01 0.005 0.001 TCP CBR (sec) M ơi t rư ờn g ti ện íc h (% ) FIFO RR Đưa ra Hình 3.14. So sánh mơi trường tiện ích trong mơ hình đa chặng Cuối cùng, hình 3.14 cho thấy sự so sánh mơi trường tiện ích của ba cơ chế với những khoảng thời gian truyền gĩi tin CBR khác nhau. Như kết quả cho thấy, so sánh với những cơ chế gốc, cơ chế đưa ra đạt được mơi trường tiện ích cao hơn. 77 KẾT LUẬN Để cải thiện cơng bằng cho mỗi luồng trong các mạng Ad Hoc khơng dây, luận văn “Bảo đảm cơng bằng luồng trong các mạng Ad Hoc khơng dây” đã nghiên cứu đưa ra một cơ chế cho phép một nút gửi vài gĩi tin của các luồng khác nhau trong một truy nhập kênh đơn thơng qua 3 chương. Chương I tập trung vào trình bày một số khái niệm, đặc điểm, cơ chế hoạt động của mơ hình mạng Ad Hoc và kiến trúc của phân lớp 802.11 DCF MAC trong mạng khơng dây. Chương II phân tích những nguyên nhân xảy ra sự khơng cơng bằng trên cả hai tầng liên kết và tầng MAC và nghiên cứu các cơ chế đã đề xuất liên quan đến việc cải thiện sự cơng bằng trong các mạng khơng dây. Chương III tập trung vào việc đánh giá, phân tích về những giải pháp nhằm đạt được sự cơng bằng cho mỗi luồng trong các mạng Ad Hoc. Luận văn đã kết hợp giữa lý luận và thực tiễn để nghiên cứu cơ chế cơng bằng trong các mạng khơng dây nhằm đưa ra một phương thức mới chi tiết hơn về vấn đề cơng bằng trong các mạng Ad Hoc, những kết quả đạt được và những tồn tại trong cơ chế hoạt động của chuẩn IEEE 802.11. Luận văn đã đưa ra một cơ chế mà yêu cầu sự thay đổi khơng lớn về phân lớp IEEE 802.11 MAC chuẩn, hai kiểu mơ hình mạng đã được tính tốn để đánh giá hiệu quả của cơ chế đưa ra và số gĩi tin lớn nhất được gửi đi trong một truy nhập kênh đơn được cố định là 4. Đầu tiên, mơ hình đơn chặng được sử dụng để chứng thực sự cải thiện khả năng thực thi ở tầng MAC. Sau đĩ, mơ hình đa chặng được sử dụng để chứng thực sự cải thiện khả năng thực thi tại tầng liên kết. Các kết quả cho thấy cơ chế đưa ra cải thiện sự cơng bằng cho mỗi luồng, tồn bộ sự thực thi, và mơi trường tiện ích của mạng. Những giải pháp đề ra cĩ tính khả thi cao vì được xuất phát từ sự phân tích và đánh giá chặt chẽ kết hợp với ứng dụng trong thực tế. Nếu được thực hiện, các giải pháp cĩ khả năng triển khai trong các hệ thống địi hỏi tính sẵn sàng cao mà khơng phụ thuộc vào cơ sở hạ tầng mạng nhằm đạt được sự cơng bằng và ổn định trong mạng. viii TÀI LIỆU THAM KHẢO Tài liệu Tiếng Anh 1. James F.Kurose and Keith W.Ross (2005), Computer Networking a top- down Approach Featuring the Internet, 3/E, ISBN 0321269764, Addison Wesley, pp. 503 - 523. 2. Gary J.Mullett (2006), Wireless Telecommunications Systems and Networks, Thomson Delmar Learning, pp. 385 - 435. 3. Hsieh HY, Sivakumar R (2001), “Performance comparison of cellular and multi-hop wireless networks”, A quantitative study. Proc ACM SIGMETRICS, Boston, pp. 113-122. 4. Katevenis M, Stefanos S, Courcoubetis (1991), “Weighted round-robin cell multiplexing in a general-purpose ATM switch chip”, IEEE Journal Selected Areas Communication, volume 9, pp. 1265-1279. 5. ANSI/IEEE Std 802.11 (1999). Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. 6. Koksal CE, Kassab H, Balakrishnan H (2000), “An analysis of short-term fairness in wireless media access protocols”, ACM SIG-METRICS, Santa Clara, CA, pp. 118-119. 7. Luo H, Lu S, Bharghavan V (2000), “A new model for packet scheduling in multihop wireless networks”, MOBICOM, pp. 76-86. 8. Jangeun J, Sichitiu ML (2003), “Fairness and QoS in multihop wireless networks”, IEEE Veh Technol Conf, volume 5, pp. 2936-2940. 9. Woo A, Culler DE (2001), “A transmission control scheme for media access in sensor networks”, MOBICOM, Rome, pp. 221-235. 10. Bharghavan V, Demers A, Shenker S, Zhang L (1994), “MACAW : A media access protocol for wireless LANs”, SIGCOMM, pp. 212-225. ix 11. Oyunchimeg Shagdar and Bing Zhang (2005), “Improving per-flow fairness in Wireless Ad Hoc Networks”, IEEE Wireless Communication and Networking Conference, New Orleans, USA, NET39-4. 12. IEEE 802.11 WG (2001), Draft Supplement to Part 11: Wireless Medium Access Control (MAC) and physical layer (PHY) specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS), IEEE 802.11e/D2.0. 13. Vardalis D (2001). On the efficiency and fairness of wired/wireless networks, Master’s thesis, State University of New York at Stony Brook, pp. 19-20. 14. USB/LBNL/VINT Networks Simulator ns (version2), 15. Choi S, del Prado J, Shankar S, Mangold S (2003), “IEEE 802.11e contention-based channel access (EDCF) performance evaluation”, Proc IEEE ICC, Anchorage, AL, pp. 1151-1156. 16. Pentikousis K (2003), “TCP in wired-cum-wireless environments”, IEEE Commun Surv, volume 3, pp. 2-14.