자동 재전송 질문이있는 강력한 직렬 프로토콜

Question

장시간 독자, 처음 포스터.

나는 블루투스를 통해 센서와 기지국 사이의 직렬 링크를 가지고있다. 블루투스 링크는 믿을 수 없을만큼 신뢰할 수없고 당신이 믿지 않는 것처럼 패킷을 떨어 뜨립니다. 나는 이것을 긍정적으로 사용하고 똥꼬 링크에서 생존 할 수있는 강력한 직렬 프로토콜을 설계하려고합니다.

나는 사무실에서 유일한 임베디드 개발자이므로 사람들의 아이디어를 바꿔주고 싶습니다.

바이트 스터핑을 사용하여 시작 (STX) 바이트와 엔드 (ETX) 바이트, 인덱스 번호 및 CRC가있는 패킷을 만드는 계획입니다. STX와 ETX 및 DLE 문자가 나올 때 이스케이프 문자 (DLE) 사용을 계획 중입니다. 그 부분은 모든 꽤 명확하고 여기

static void SendCommand(struct usart_module * const usart_module, uint16_t cmd, 
     uint8_t *data, uint8_t len) 
{ 
    //[STX] ({ [IDX] [CMD_H] [CMD_L] [LEN] ...[DATA]... } [CRC]) [ETX] // Data in {} brackets is XORed together for the CRC. // Data in() is the packet length 
    static uint8_t idx; 
    uint8_t packet[256]; 
    uint8_t crc, packetLength, i; 

    if (len > 250) 
     return; 

    packetLength = len + 5; 

    packet[0] = idx++; 
    packet[1] = (cmd >> 8); 
    packet[2] = (cmd & 0x00FF); 
    packet[3] = packetLength; 

    crc = 0; 
    for (i = 0; i <= 3; i++) 
    { 
     crc ^= packet[i]; 
    } 

    for (i = 0; i < len; i++) 
    { 
     packet[4 + i] = data[i]; 
     crc ^= data[i]; 
    } 

    packet[4 + len] = crc; 

    // Send Packet 
    uart_putc(usart_module, STX); 
    for (i = 0; i < packetLength; i++) 
    { 
     if ((packet[i] == STX) || (packet[i] == ETX) || (packet[i] == DLE)) 
     { 
      uart_putc(usart_module, DLE); 
     } 
     uart_putc(usart_module, packet[i]); 
    } 
    uart_putc(usart_module, ETX); 
} 

그래서 그 패킷을 보낼 것을해야 할 코드가 있다고,하지만 지금은 패킷을 추적하고 자동으로 실패한 사람을 재전송하는 몇 가지 코드를 추가해야하고 그게 내가 몇 가지 아이디어가있는 도움이 필요한 곳.

몇 가지 옵션이 있습니다. -Easiest, 패킷을 저장하고 패킷을 전송 한 후 버퍼에 넣고 충분한 시간이 지난 후에 ACK를 받으면 256 패킷의 거대한 배열을 할당하십시오. 그럼 내가 ACK를받을 경우 항목이 비어 있도록 배열에서 해당 레코드를 삭제하면 잘 받았습니다. 그와

문제는 내가 256 바이트, 그 중 256 개 인스턴스의 최악의 경우 패킷 크기를 사용하는 경우, RAM의 64 K 이잖아 그리고 난 그걸 해달라고 (내가 않은 경우에도 끔찍한 생각 이잖아)이다

다음 아이디어, 모든 패킷의 링크 된 목록을 만들고 malloc 명령 등을 사용하여 메모리를 동적으로 할당하고 승인 된 패킷을 제거하고 x 시간 이후에 재전송 할 패킷을 알 수 있도록 보관하십시오.

문제점 전체 malloc 아이디어가 있습니다. 솔직히, 나는 그것을 사용한 적이 없으며 제한된 메모리가있는 임베디드 환경에서 사용하는 아이디어를 좋아하지 않습니다. 어쩌면 그저 바보 같아 보이지만, 내가 필요로하는 다른 문제의 양동이로드에 문을 열어주는 느낌.

-Protential 솔루션은 위의 모든 패킷에 대해 링크 된 목록을 만들지 만, FIFO에서 만들고 모든 레코드를 이동하여 FIFO에 보관합니다.

송신 패킷 1, 송신 패킷 3 아무것도
안함,
패킷 1에 대해 NACK을 수신 FIFO에있는 FIFO에서의
전송 패킷 2 넣어 패킷을 패킷 넣어
가 ACK를 수신 FIFO에서 패킷을 넣어 패킷 2 FIFO
에서 × 00 행 memset 함수 패킷 2 FIFO
송신 패킷 4 × 00로 패킷 3 memset 함수 패킷 2에 대한 ACK를 수신 FIFO에있는 패킷을 넣어
송신 패킷 (5), FIFO
에서 패킷을 넣어 FIFO에 더 이상 여유 공간이 없으므로 패킷 2와 3이 지금 비어있는 상태이므로 모든 것을 앞뒤로 뒤섞습니다.

실시간으로 셔플을 유지할 수 있지만 모든 패킷이 수신 된 후에 전체 FIFO를 셔플해야하므로 불필요한 작업이 많이 발생합니다.

내가 찾고있는 것은 "Jeez Ned, 나쁘지는 않지만 단지 xyz 만하면 작업 또는 RAM 또는 복잡성의 힙을 절약 할 수 있습니다"라고 말하기위한 것입니다.

단지 몇 명의 사람들이 아이디어를 얻어 내고 싶다면 어떻게하면 일반적으로 가장 좋은 해결책을 얻을 수 있을까요? 나는 내 솔루션을 좋아하지만 뭔가를 놓치고있는 것처럼 느껴진다. 확실하지 않다 ... 나는 다만 생각하지 않는다이 아이디어에 100 % 행복하게 느낀다, 그러나 다만 기울기는 더 나은 방법을 생각한다.

Answer 1

malloc을 사용할 필요가 없습니다. 그냥 구조체 배열로 모든 패킷을 정적으로 할당하십시오. 그러나 배열을 사용하여 런타임에 패킷을 반복하지 마십시오. 오히려 연결된 목록 아이디어를 확장하십시오. 두 개의 목록을 만듭니다. 하나는 ACK를 기다리는 패킷을위한 것이고 다른 하나는 사용 가능한 (즉, 사용 가능한) 패킷을위한 것입니다. 시작할 때 모든 패킷을 프리리스트에 추가하십시오. 패킷을 보낼 때 빈 목록에서 패킷을 제거하고 대기중인 ACK 목록에 추가하십시오. awaiting-ACK리스트를 이중 링크로 만들면 목록의 중간에서 패킷을 제거하고이를 프리리스트로 되돌릴 수 있습니다.

패킷 크기가 크게 다르며 더 적은 메모리로 더 많은 패킷을 지원하려는 경우 다른 크기의 패킷에 대해 여러 개의 자유 목록을 만들 수 있습니다. 예를 들어, max-size-free-list는 가장 큰 패킷을 보유하고 economy-size-free-list는 더 작은 패킷을 보유합니다. awaiting-ACK리스트는 어느 프리 -리스트가 패킷을 리턴 하는지를 알 수있는 한 두 가지 크기를 가질 수있다. 패킷 구조체에 플래그를 추가하여이를 알 수 있습니다.

typedef enum PacketSizeType 
    PACKET_SIZE_MAX = 0, 
    PACKET_SIZE_ECONOMY 
} PacketSizeType; 

typedef struct PacketBase{ 
    PacketBase * next; 
    PacketBase * prev; 
    PacketSizeType type; 
    uint8_t data[1]; // a place holder (must be last) 
} PacketBase; 

typedef struct PacketMax 
{ 
    PacketBase base; // inherit from PacketBase (must be first) 
    uint8_t data[255]; 
} PacketMax; 

typedef struct PacketEconomy 
{ 
    PacketBase base; // inherit from PacketBase (must be first) 
    uint8_t data[30]; 
} PacketEconomy; 

PacketMax MaxSizedPackets[100]; 
PacketEconomy EconomySizedPackets[100]; 
Packet *free_list_max; 
Packet *free_list_economy; 
Packet *awaiting_ack_list; 

초기화 코드는 사이클 두 배열을 통해, MAX 또는 ECONOMY 중 하나에 base.type 멤버를 설정하고 적절한 자유 목록에 패킷을 추가해야합니다. 전송 코드는 적절한 크기의 프리리스트로부터 패킷을 가져와이를 대기중인 ACK리스트로 이동시킨다. awaiting-ACK 목록에는 두 유형의 패킷이 모두 포함될 수 있습니다. 둘 다 PacketBase에서 상속되기 때문입니다. ACK 처리기 코드는 base.type을 검사하여 패킷을 적절한 빈 목록으로 반환해야합니다.

Answer 2

몇 노트.

• 주문을 고려해야합니다. 순서가 맞지 않는 배송은 받아 들일 수 있습니까?
• 중복 패킷을 신경 써야합니까?
• 손실 된 ACK는 시간 초과로 감지되어야합니다.

제 생각에는 패킷 배달 순서에 신경 쓰고 중복 패킷을 원하지 않는 것 같습니다.

기본 접근법은 시퀀스 번호가있는 패킷을 보내고 일정 시간 내에 ACK를 기다리는 것입니다. ACK를 받으면 순서대로 다음 패킷을 보냅니다. ACK를 얻지 못하면 (타임 아웃과 NAK를 고려하십시오) 그런 다음 재전송하십시오. 반복.

해결되지 않은 패킷이있는 동안 데이터 구조 문제가 응용 프로그램에서 대기열에 들어갑니다.

미해결 된 여러 패킷을 얻으려면보다 복잡한 데이터 구조와 선택적 ACK를 수행해야합니다. 거기에 많은 문학이 있지만 시작하기 좋은 곳은 Tannenbaum의 "Computer Networks"입니다.